Automata, Languages, and Decision Procedures

Vocabulary review of automata, languages, strings, and acceptance from the lecture notes.

Automaton

An abstract machine consisting of states that processes input strings to decide whether the string belongs to a particular language.

State

A configuration within an automaton that, through transitions on input, participates in deciding whether a given word is in the language.

Language

A set of strings (or words) over an alphabet; the collection of inputs that an automaton may decide membership for.

String (Word)

A finite sequence of symbols (letters) from an alphabet.

Decision procedure

The process that, given a word, outputs yes if the word is in the language and no otherwise.

Acceptance

A word is accepted when the automaton (via its state) answers yes for that word; accepted words are exactly those in the language.

Acceptance vs language

A common mistake is saying the automaton 'accepts the language'; more precisely, a state accepts individual words, and the language is the set of all accepted words.

Input (Word) vs words

Input refers to the string fed to the automaton; automata read sequences of inputs (words) to decide membership.

Solution space

The set of inputs that are accepted by the automaton, interpreted as the solution space to the corresponding decision problem.

Puzzle games (motivating example)

A motivating example where a puzzle game processes a sequence of inputs and yields a yes/no decision, illustrating decision procedures for languages.