Automata theory Study Guide

📖 Core Concepts Automaton – a self‑acting machine that reads input symbols and moves between a finite set of states according to a transition rule. Finite Automaton (FA / FSM) – an automaton with a limited number of states; represented by circles (states) and arrows (transitions). Transition function – maps a current state + current input symbol → next state. Accepting (final) state – a state where the automaton stops and accepts the input string. Language recognized – the set of all strings that cause the automaton to finish in an accepting state. Deterministic vs. Nondeterministic – DFA: one unique next state for each state‑symbol pair; NFA: possibly many next states (described by a transition relation). Pushdown Automaton (PDA) – adds a stack (push/pop) to a finite‑state control, enabling recognition of context‑free languages. Turing Machine (TM) – a tape‑based automaton with unlimited read/write tape; the most powerful model in the Chomsky hierarchy. Chomsky hierarchy – classification of language families (regular ⊂ context‑free ⊂ context‑sensitive ⊂ recursively enumerable) matched to increasingly powerful automata. 📌 Must Remember Myhill–Nerode theorem → a language is regular iff it has a finite number of equivalence classes; the number of classes equals the minimal DFA state count. Pumping lemma for regular languages – any sufficiently long string $w$ in a regular language can be split $w = xyz$ with $|xy| \le p$, $|y|>0$, and $xy^{i}z$ also in the language for all $i\ge0$. DFA ≡ NFA – every NFA has an equivalent DFA (subset construction). DPDA‑I < NPDA‑I – one‑stack deterministic PDA is strictly weaker than its nondeterministic counterpart. DPDA‑II ≡ NPDA‑II ≡ DTM – two‑stack deterministic/ nondeterministic PDAs are computationally equivalent to a deterministic Turing machine. All TM variants (NTM, PTM, MTM, multidimensional TM) have the same computational power as a DTM. 🔄 Key Processes Subset Construction (NFA → DFA) Start with the NFA’s start state as the DFA’s start subset. For each DFA state (a set of NFA states) and each input symbol, compute the union of all NFA transitions; this becomes a new DFA state. Repeat until no new subsets appear; mark any DFA state containing an NFA accepting state as accepting. Minimizing a DFA (via Myhill–Nerode) Partition states into accepting vs. non‑accepting groups. Iteratively split groups: two states stay together only if, for every input symbol, their transitions lead to states in the same current group. When partitions stop changing, each block is a single state of the minimal DFA. Applying the Pumping Lemma Choose a string $w$ longer than the pumping length $p$. Show every possible split $w=xyz$ (with constraints) leads to a contradiction when pumping $y$ (i.e., $xy^{i}z \notin L$ for some $i$). 🔍 Key Comparisons DFA vs. NFA – DFA: one next state per symbol; NFA: many possible next states (including ε‑moves). DPDA‑I vs. NPDA‑I – DPDA‑I: deterministic, single stack, cannot recognize all CFLs; NPDA‑I: nondeterministic, single stack, can recognize all CFLs. DPDA‑II vs. NTM – Both have full Turing‑complete power; the extra stack gives a TM‑equivalent tape. Finite Automaton vs. Pushdown Automaton – FA: no auxiliary memory (regular languages); PDA: one stack memory (context‑free languages). ⚠️ Common Misunderstandings “NFA is weaker than DFA.” – Wrong; they have equal expressive power (only the description size differs). “All nondeterministic machines are more powerful.” – Only true when the memory model changes (e.g., NFA vs. DFA). NTM vs. DTM are equal in power. “A PDA can recognize any language.” – Only languages that are context‑free; languages requiring two stacks need a TM. 🧠 Mental Models / Intuition State diagram as a road map – each circle is a city (state); arrows are one‑way streets labeled by input symbols. Traversing the map with a string is like driving a car; you finish in a “goal city” (accepting state) to succeed. Stack as a “memory of past calls” – think of a program’s call stack; push when you need to remember a symbol, pop when you match it later (e.g., matching parentheses). 🚩 Exceptions & Edge Cases ε‑transitions in NFAs can cause “silent” moves; they must be closed (ε‑closure) before applying the subset construction. Empty language – a DFA with no accepting states recognizes nothing; still a valid regular language. Infinite input strings – automata can be defined for infinite words (ω‑automata), but the outline only covers finite inputs. 📍 When to Use Which Lexical analysis / token scanning – use a DFA (fast, table‑driven). Proving a language is not regular – apply the pumping lemma or Myhill–Nerode. Parsing programming languages – employ a pushdown automaton (or equivalently, a CFG parser). Designing algorithms that need arbitrary computation – model with a Turing machine (or any TM variant). 👀 Patterns to Recognize Regular language clues – limited nesting, no need for matching arbitrary pairs; often described by simple regexes. Context‑free pattern – balanced parentheses, nested structures, recursion in grammar. State‑equivalence – two states that behave identically on all future inputs belong in the same Myhill–Nerode class → can be merged. 🗂️ Exam Traps “All nondeterministic machines are more powerful.” – Distractor; only true when the memory model changes (e.g., NFA vs. DFA, but NTM vs. DTM are equal). Confusing deterministic with minimal – A DFA can be deterministic yet non‑minimal; you must still run minimization. Misapplying the pumping lemma – Students often pick a string shorter than the pumping length $p$ or ignore the $|xy| \le p$ restriction. Assuming a PDA with one stack can simulate a TM – Wrong; you need two stacks (or a tape) for Turing‑complete power. --- Use this guide for a quick, confidence‑boosting review right before your automata theory exam.