Automata are small abstract machines that read a string and accept or reject it; formal languages are the sets of strings they accept. Together they classify how complicated a pattern is and what kind of machine can recognise it. They sit under regular expressions, lexers, parsers and protocol checkers.
Key concepts
- Finite automata: a fixed number of states and no other memory; they recognise exactly the regular languages.
- Regular expressions: a notation for the same languages, convertible to and from automata.
- Pushdown automata: a finite automaton with a stack; they recognise context-free languages, such as nested brackets.
- Chomsky hierarchy: regular, context-free, context-sensitive and recursively enumerable languages, each needing a stronger machine.
- Closure and pumping: which operations keep a language in its class, and how to prove a language is not in it.
Vocabulary
- Alphabet and string: the symbols allowed, and a finite sequence of them.
- DFA and NFA: deterministic and nondeterministic finite automata; they accept the same languages.
- Grammar: a set of rewriting rules that generates the strings of a language.
- Parse tree: the structure a grammar assigns to one string.
What to study, in order
- Draw a DFA for strings with an even number of zeros, then code it as a table.
- Convert an NFA to a DFA by the subset construction and a regular expression to an NFA.
- Use the pumping lemma to prove that balanced brackets are not regular.
- Write a context-free grammar and a recursive-descent parser for arithmetic.
- Place each class on the Chomsky hierarchy and link it to the Turing machine.