Lesson 9 of 11Article15 min
Automata & Formal Languages Preview
You do not need full theory here — learn the landscape so algorithms and compilers courses feel connected to discrete foundations.
Machines that recognise patterns
You do not need full theory here — learn the landscape so algorithms and compilers courses feel connected to discrete foundations.
- DFA/NFA: finite memory recognisers for regular languages.
- Regular expressions ↔ finite automata (Kleene).
- Context-free grammars / pushdown automata for nested structure (e.g. balanced parentheses).
- Turing machines: the standard model of computability.
Undecidability results (halting problem) show hard limits: some questions no algorithm can answer for all inputs.