Theory of Computation · ODD 2026 · Regular Languages & Automata

Regular Languages

How the regular-language toolkit fits together — for orientation and review, not first-time reading. Pair this with the lecture notes for the “why,” and the flashcards for recall.

Regular Languages Machines Building a DFA Minimization Regex ↔ Automata Proving Non-Regularity DFA NFA ε-NFA Subset construction Four-step method Product construction Complement (swap F) Dead / trap state Distinguishable states Table-filling Myhill–Nerode ∼L Minimal DFA Thompson's construction ε-elimination Regex → NFA NFA → DFA Pumping lemma Adversary game Pigeonhole on states Closure-based proof
How the regular-language toolkit fits together: three machines that all recognize the same class (DFA, NFA, ε-NFA), the method for building or minimizing one, the bridge that turns a regular expression into an automaton and back, and the one tool — the pumping lemma — for proving a language doesn't belong at all.
Machines Building a DFA Minimization Regex ↔ Automata Proving Non-Regularity
AI-generated study aid. This mind map was generated with AI assistance and has been reviewed, but it may still contain small errors. If you spot one, please report it so it can be corrected.