Part of the Computer Science curriculum.
Four nested levels of grammar and language complexity — regular, context-free, context-sensitive, and unrestricted — that organize everything the rest of this discipline develops in real depth for the first two.
A set of production rules — some referencing themselves, exactly the self-referential shape already familiar from recursion — that generate every string in a language one substitution at a time.
A grammar is ambiguous when some string it generates has more than one valid derivation tree — a real, practical problem for anything built on a grammar, from a calculator's operator precedence to a compiler's parser.
Every context-free grammar can be rewritten into one where every rule has exactly one of two fixed shapes — a standardized form that makes later proofs and parsing algorithms possible without losing any generating power.
A machine with a finite set of states, no memory beyond which state it's in, and exactly one transition per symbol — the simplest formal model of computation, and the one that recognizes exactly the regular languages.
A machine allowed to have several transitions for the same symbol at once, or none at all — accepting when SOME choice of path leads to acceptance, a looser rule that turns out not to add any real power.
An NFA given exactly one extra resource — a single stack — which is precisely enough additional memory to recognize every context-free language, and not one language more.
Pushdown automata and context-free grammars recognize exactly the same class of languages — two very different-looking formalisms, one procedural and one generative, that turn out to be two views of the same thing.
Every NFA, however tangled its nondeterminism looks, can be converted into an equivalent DFA by tracking every state the NFA COULD be in at once as a single new state — a genuinely surprising result, proved here in full.
Combining two regular languages with union, concatenation, or Kleene star always produces another regular language — a set of guarantees that make it possible to build a complex regular language out of simple, already-known-regular pieces.
A compact notation for describing a language directly, built from single symbols, concatenation, union, and repetition — the same expressive power as a DFA, in a form that reads like a pattern instead of a machine.
Building an NFA for a regular expression piece by piece, mirroring its structure exactly — the constructive, straightforward half of Kleene's theorem, proving every regex has an equivalent automaton.
Every regular language has a length past which any long enough string must contain a repeatable middle section — a precise, provable structural fact whose contrapositive is the standard tool for proving a language is NOT regular.
The same pumping idea, one level up the Chomsky hierarchy — a long enough string in a context-free language must have two repeatable pieces, pumped together, giving a standard tool for proving a language is not even context-free.
The harder direction of Kleene's theorem — eliminating a DFA's states one at a time, building up a regular expression that captures the same language, until only the expression itself remains.
Two everyday, extremely well-known payoffs of everything covered so far — search-and-replace tools running compiled regular expressions, and a programming language's own syntax defined and parsed by a context-free grammar.
Every model covered here — DFA, NFA, PDA — is fundamentally limited: a fixed amount of memory, or memory shaped only like a single stack. The next discipline removes that limit entirely with the Turing machine.