Automata and Formal Languages

Corresponds to Sipser, Chapters 1–2 (Part One: Automata and Languages). The two weakest, most tractable models of computation, each paired with an equally-expressive grammar/expression formalism. A finite automaton reads an input and accepts or rejects with no memory beyond its current state; nondeterministic finite automata (NFAs) are no more powerful than deterministic ones (DFAs) but are often far easier to design, and regular expressions give a third, declarative way to describe the exact same class of languages. The pumping lemma is the standard tool for proving a language is not regular, by showing every long enough string in it can be “pumped” (a substring repeated) while staying in the language — something a finite automaton’s finite memory can’t prevent. Pushdown automata add a single unbounded stack, exactly matching the power of context-free grammars (used to describe nested/recursive structure, e.g. balanced parentheses or programming-language syntax), with its own pumping lemma for proving non-context-freeness, and the deterministic subclass (parseable without backtracking, e.g. via LR(k) parsing) underlying real compilers.

Outline (TODO — flesh out each)

• Finite automata — formal definition, examples, designing one
• The regular operations
• Nondeterminism — NFAs, equivalence with DFAs, closure under regular operations
• Regular expressions — equivalence with finite automata
• Nonregular languages — the pumping lemma for regular languages
• Context-free grammars — definition, examples, ambiguity, Chomsky normal form
• Pushdown automata — definition, examples, equivalence with CFGs
• Non-context-free languages — the pumping lemma for context-free languages
• Deterministic context-free languages — DPDAs, DCFGs, LR(k) parsing