Finite automata and formal languages: grammars and regex

In short: Finite automata recognise simple language patterns (regular expressions), pushdown automata and context-free grammars describe programming languages, Turing machines compute everything computable.

In more detail: Theoretical computer science explains what computers can do in principle. Practice: regex, parsers/compilers, protocols, game AI (state machines) and exam topics (state diagrams).

In Depth

Finite automaton (DFA/NFA)

A finite automaton has states, an alphabet, transitions, a start state and accepting states. It reads a word character by character and accepts if it ends in an accepting state. Example: binary words with an even number of ones: states even (start, accepting) and odd; on 1 switch, on 0 stay. DFA (deterministic) vs. NFA (nondeterministic, several successor states/ε-transitions): both recognise the same languages (regular languages), NFAs can be converted into DFAs (powerset construction). It has no memory except the current state: it cannot count “equally many a and b”.

Regular expressions

Equivalent to finite automata: a|b, a*, a+, a?, [0-9]{4}. Engines convert regex into automata (Thompson construction). Practical regex have backreferences/lookahead and are more powerful/unsafer (ReDoS: catastrophic backtracking). Limits: nested brackets, HTML/JSON/program code are not regular: you need a parser for them.

Chomsky hierarchy

1. Type 3 – regular (automaton, regex): tokens, numbers, email patterns.
2. Type 2 – context-free (pushdown automaton, grammar like BNF/EBNF): programming languages, JSON, bracket expressions.
3. Type 1 – context-sensitive.
4. Type 0 – general (Turing machine). Example grammar: Expression → Number | Expression '+' Expression | '(' Expression ')' (generates bracket/sum expressions). Compiler: lexer (type 3) → parser (type 2) → syntax tree.

Turing machine and limits

• Turing machine: tape, read/write head, states; model of what is computable (Church-Turing thesis). Every programming language is Turing-complete (with loop/memory).
• Halting problem: there is no program that decides for every program whether it halts (undecidable).
• Complexity classes P, NP (see P and NP).
• Practice: state machines (traffic light, game AI, protocols, UI states), parser generators (ANTLR), syntax highlighters, validation of inputs.
• Exam (IHK/AP): read/draw a state diagram, check a word, interpret a regex.

See also: Regex, Lexer, parser and syntax tree, State machine, P and NP