Regular · Context-free · Turing

Automata Theory

Abstract machines recognize language families: DFAs/NFAs for regular languages, PDAs for context-free languages, and Turing machines for computable languages.

Overview Fundamentals Guides Applications Examples FAQ

📘 Overview

Automata provide minimal mathematical models of computation. They help reason about what patterns can be recognized with limited memory and how grammars generate languages.

📚 Layers

Regex/DFAs: finite memory
CFG/PDAs: stack memory
Turing machines: general computation

🛠️ Guides

From Regex to DFA

Thompson construction → NFA
Subset construction → DFA
Minimize DFA by partition refinement

Proving Non-Regularity

Pumping lemma contradictions
Myhill–Nerode equivalence classes

🌍 Applications

Lexers/parsers: compilers and interpreters
Protocol verification: model checking
Input validation: regex-based sanitization

🧪 Examples

Language aⁿbⁿ: not regular, but context-free
Balanced parentheses: PDA with stack pushes/pops
Palindromes over {0,1}: requires more than DFA

❓ Frequently Asked Questions

1) NFA vs DFA power?
Equivalent for regular languages; NFAs can be exponentially smaller.

2) Are context-free languages closed under intersection?
Not with each other; but with regular languages, yes.

3) Undecidability?
Halting problem shows limits of computation.

4) Why minimization?
Smallest DFA improves performance and clarity.

5) Ambiguous grammars?
Different parse trees for same string; use unambiguous forms.

6) Deterministic PDA?
Strictly less powerful than general PDA.

7) LR vs LL parsing?
Bottom-up vs top-down parsing strategies.

8) Regex features beyond regular?
Backreferences make some regex engines non-regular.

9) Chomsky hierarchy?
Regular ⊂ Context-free ⊂ Context-sensitive ⊂ Recursively enumerable.

10) Tools?
Lex/Yacc, ANTLR, Ragel for building language tooling.