Difficulty: Advanced | Prerequisites: Chapters 3-5 (algorithms, induction), basic set notation
Tags: DFA, deterministic finite automaton, NFA, nondeterministic finite automaton, regular language, regular expression, context-free language, context-free grammar, production rule, pushdown automaton, Turing machine, halting problem, undecidable, computability, language, string, alphabet, transition graph, lambda transition, accept, reject, Church-Turing thesis, CS182, discrete math, Purdue
This chapter asks: what can computers actually compute? Finite automata are the simplest model, recognising patterns like "does this string match a regular expression?" Pushdown automata add a stack and can handle nested structures like balanced parentheses. Turing machines have unlimited memory and can compute anything that is computable at all, yet some problems (like the halting problem) remain forever out of reach. This material connects directly to compiler design, formal verification, and the theoretical limits of computing. You should be comfortable with sets, strings, algorithms, and induction.
Finite automata (DFAs and NFAs) recognise regular languages and have no working memory. Pushdown automata recognise context-free languages using a stack. Turing machines recognise the broadest class of languages and model any algorithm. The halting problem proves that some problems are undecidable: no algorithm can solve them.
Alphabet (Σ)
A finite set of characters. Example: Σ = {a, b} or Σ = {0, 1}.
String
A finite sequence of characters from an alphabet. Example: "aab" has length 3.
λ (lambda / empty string)
The string with no characters. Its length is 0. λ is in Σ* but not in Σ.
Σ (Kleene star)*
The set of all possible strings over alphabet Σ, including the empty string. Σ* is always infinite.
Language
Any subset of Σ*. A language can be finite or infinite.
Concatenation
Joining two strings end to end. If u = "ab" and v = "cd," then uv = "abcd."
Deterministic Finite Automaton (DFA)
A machine with a finite set of states, a start state, a set of accepting (final) states, and a transition function that maps each (state, input symbol) pair to exactly one next state. It reads input left to right, one symbol at a time, and accepts if it ends in a final state. In simple terms, a DFA is a flowchart with no choices: for each state and each input symbol, there is exactly one arrow to follow.
Nondeterministic Finite Automaton (NFA)
Like a DFA but with two added possibilities: from one state, multiple transitions on the same symbol (or no transition at all), and lambda transitions (moving to a new state without reading input). An NFA accepts a string if there exists at least one path through the machine that ends in an accepting state. Think of it as a DFA that can guess the right path.
Lambda transition (ε-transition)
A transition in an NFA that changes state without consuming any input symbol. The read head does not move.
Regular language
A language that can be recognised by a DFA (equivalently, by an NFA, or described by a regular expression). DFAs, NFAs, and regular expressions have the same expressive power.
Transition graph
A directed graph representing an automaton. States are vertices, transitions are labelled edges. The start state has an incoming arrow from nowhere; accepting states are drawn with a double circle.
Context-free grammar (CFG)
A set of production rules G = (V, T, S, P) where V is a set of variables, T is a set of terminals, S is the start variable, and P is a set of production rules. Each rule replaces a variable with a string of variables and terminals.
Derivation
A sequence of rule applications starting from S and ending with a string of terminals. A leftmost derivation always expands the leftmost variable first.
Context-free language
A language generated by some context-free grammar. Context-free languages include all regular languages plus languages like {aⁿbⁿ : n >= 0} that regular languages cannot express.
Pushdown automaton (PDA)
A finite automaton augmented with an infinite stack. It can push symbols onto and pop symbols off the stack. PDAs recognise exactly the context-free languages.
Turing machine (TM)
A theoretical machine with an infinite tape, a read/write head, and a finite set of states. At each step, it reads the current tape symbol, writes a new symbol, moves the head left or right, and transitions to a new state. It is the most powerful standard model of computation.
Halting
A Turing machine halts when it reaches a state with no applicable transition. It accepts if it halts in a final state, rejects if it halts in a non-final state or enters an infinite loop.
Universal Turing Machine
A Turing machine that can simulate any other Turing machine, given a description of that machine and its input on the tape. This is the theoretical basis for general-purpose computers.
Turing thesis (Church-Turing thesis)
Any algorithmic procedure that can be carried out by a human or computer can be carried out by a Turing machine. This is a hypothesis, not a proven theorem.
Halting problem
Given a Turing machine M and input w, determine whether M halts on w. This problem is undecidable: no Turing machine can solve it for all (M, w) pairs.
Countable / Uncountable sets
Finite sets and sets with a one-to-one correspondence with the natural numbers are countable (e.g. integers, rationals, Σ*). The set of all languages over Σ is uncountable. Since the set of Turing machines is countable but the set of languages is uncountable, some languages have no Turing machine that recognises them.
Automata are classified by their working memory:
Finite automaton: no temporary memory. Recognises regular languages.
Pushdown automaton: infinite stack memory. Recognises context-free languages.
Turing machine: infinite tape memory. Recognises recursively enumerable languages (the broadest class).
Each successive type is strictly more powerful.
Strings are built from an alphabet Σ:
Concatenation: uv joins u and v
Reverse: the characters of a string in reverse order
wⁿ = w repeated n times; w⁰ = λ
Σ* = {λ, a, b, aa, ab, ba, bb, aaa, ...} for Σ = {a, b}
A language L is any subset of Σ*
Operations on languages: union, intersection, difference, complement (Σ* - L).
Important distinction: the empty set ∅ = {} is not the same as {λ}. The empty set has size 0; {λ} has size 1.
A DFA has:
A finite set of states
An alphabet Σ
A transition function δ(state, symbol) → state
A start state q₀
A set of accepting (final) states F
The DFA reads input one symbol at a time, transitions deterministically, and accepts if it finishes in a final state.
Example: L(M) = {all strings with prefix "ab"} over Σ = {a, b}. The DFA has states tracking whether it has seen "a" then "b" at the start.
Example: L(M) = {all strings without "001"} over Σ = {0, 1}. States track how much of "001" has been seen so far; reaching a state that has seen the full "001" goes to a permanent reject (trap) state.
An NFA differs from a DFA in two ways:
From one state, there can be multiple transitions on the same symbol (or zero transitions)
Lambda transitions allow state changes without consuming input
Acceptance: an NFA accepts a string if there exists at least one sequence of transitions that consumes the entire input and ends in an accepting state. A single accepting path suffices, even if other paths reject or hang.
Rejection: an NFA rejects when no computation path accepts (every path either ends in a non-final state or cannot consume all the input).
Example NFA with Σ = {a}: from q₀, on input "a," the NFA can go to q₁ or q₃. From q₁, on "a," it goes to q₂ (accepting). From q₃, there is no transition. Input "aa" is accepted because the path q₀ → q₁ → q₂ reaches an accepting state.
Key theorem: DFAs and NFAs recognise exactly the same class of languages (the regular languages). Every NFA can be converted to an equivalent DFA (though the DFA may have exponentially more states).
A lambda transition moves to a new state without reading input. The read head stays in place.
Example: L = {(ab)ⁿ : n >= 1}. An NFA reads "a," transitions to a state, reads "b," then takes a lambda transition back to replay the pattern.
Example: L(M) = {10}* = {λ, 10, 1010, 101010, ...}. An NFA with a lambda transition looping back after reading "10."
Regular languages are exactly those recognised by DFAs, NFAs, and regular expressions. All three formalisms are equivalent.
Examples of regular languages: a*, ab, strings containing "aba," strings of even length.
Example of a language that is NOT regular: {aⁿbⁿ : n >= 0}. This requires counting, which finite automata cannot do (no memory to track how many a's were seen).
A grammar G = (V, T, S, P):
V: variables (uppercase letters, e.g. S, A, B)
T: terminals (lowercase letters, e.g. a, b)
S: start variable
P: production rules (e.g. S → aSb, S → λ)
Derivation: start from S, apply rules until only terminals remain.
Example: G with S → Ab, A → aAb, A → λ.
S ⇒ Ab ⇒ b (using A → λ)
S ⇒ Ab ⇒ aAbb ⇒ abb
S ⇒ Ab ⇒ aAbb ⇒ aaAbbb ⇒ aabbb
This generates L(G) = {aⁿbⁿ⁺¹ : n >= 0}.
Example: grammar for arithmetic expressions can generate ((v + (v v)) (v - v)).
Leftmost derivation: always expand the leftmost variable. Rightmost derivation: always expand the rightmost. Both produce the same language.
Context-free languages properly contain regular languages. {aⁿbⁿ} is context-free but not regular. Context-free languages are recognised by pushdown automata.
Regular languages ⊂ Context-free languages ⊂ Languages accepted by Turing machines
Regular: a*, ab
Context-free but not regular: aⁿbⁿ, wwᴿ (palindromes)
Turing-recognisable but not context-free: aⁿbⁿcⁿ, ww
A Turing machine has:
A finite set of states
An infinite tape (input/output/working memory)
A read/write head that moves left or right one cell per step
A transition function: given current state and tape symbol, write a new symbol, move the head, and enter a new state
Halting: the machine halts when no transition applies. Accepts if in a final state; rejects if in a non-final state. It can also loop forever (never halt).
Deterministic TMs only: each (state, symbol) pair has at most one transition. Nondeterministic transitions are "not allowed" in the standard model (though nondeterministic TMs are studied theoretically and have the same power).
Example: TM for language aa* (one or more a's). On reading "a," move right and stay in the accepting path. On reading a blank, halt and accept.
Example: TM for L = {w : w = aⁿ with n > 0 or w = b{a,b}*}. Read "a" and keep going right; if you hit a blank, accept. Read "b" as the first character and accept anything after.
A single Turing machine that can simulate any other TM. Its input is an encoding of the target TM's transition table plus the target TM's input.
A Turing machine's transitions can be encoded as a binary string (states encoded in unary, symbols in binary, separators between fields). The set of all TM encodings is a language, and this language is countable.
Σ* is countably infinite (strings can be enumerated).
The set of all languages (subsets of Σ*) is uncountably infinite.
The set of Turing machines is countable (each is a finite binary encoding).
Therefore, there are languages for which no Turing machine exists. These languages correspond to undecidable problems.
The halting problem: given a TM description M and an input w, determine whether M halts on w. This is undecidable, proven by diagonalisation. No algorithm can solve it in general.
Any algorithmic procedure that a human or computer can perform can be performed by a Turing machine. This is a philosophical hypothesis, not a theorem, but no counterexample has ever been found. There is no known model of computation more powerful than Turing machines.
Same power does not mean same speed. A two-tape TM can recognise {aⁿbⁿ} in O(n) time, while a standard one-tape TM needs O(n²).
DFA: (Q, Σ, δ, q₀, F) where δ is a total function
NFA: (Q, Σ, δ, q₀, F) where δ maps to subsets of Q and allows λ-transitions
Grammar: G = (V, T, S, P)
Turing machine transition: (current state, read symbol) → (new state, write symbol, head direction)
Language hierarchy: Regular ⊂ Context-free ⊂ Turing-recognisable
DFAs power regular expression engines in text editors, compilers (lexical analysis), and network packet filters. Context-free grammars define the syntax of every programming language; compilers use parsers (pushdown automata) to check and process code. Turing machines are the theoretical foundation of all general-purpose computing. The halting problem explains why you cannot write a program that perfectly detects infinite loops in other programs.
"NFAs are more powerful than DFAs." They are not. They recognise exactly the same languages. NFAs are often more convenient to design, but they can always be converted to DFAs.
"A Turing machine always halts." It can loop forever. Halting is not guaranteed.
"The halting problem means some programs loop forever." The halting problem says something stronger: there is no algorithm that can determine, for every (program, input) pair, whether the program halts. Individual programs may or may not halt; the issue is that no single decider works for all of them.
"Context-free grammars can describe any language." They cannot. {aⁿbⁿcⁿ} is not context-free.
"Lambda transitions consume the empty string." Lambda transitions do not read any input at all. The read head does not move.
⚠️ Be able to design a DFA or NFA for a given language and trace its execution on sample strings.
⚠️ Know the equivalence: DFA = NFA = regular expressions in power.
⚠️ Be able to write a context-free grammar for a given language and perform derivations.
⚠️ Understand the hierarchy: regular ⊂ context-free ⊂ Turing-recognisable, with examples at each level.
⚠️ Know what "undecidable" means and why the halting problem is undecidable.
⚠️ Understand that an NFA accepts if ANY path accepts; it rejects only if ALL paths reject.
True or False: Every DFA is also an NFA.
Fill in the blank: The language {aⁿbⁿ : n >= 0} is ______ but not ______.
True or False: A Turing machine always halts on every input.
Fill in the blank: An NFA accepts a string if there is at least one ______ that ends in an accepting state.
True or False: The set of all languages over {0, 1} is countable.
Answers: 1. True (a DFA is a special case of an NFA with no nondeterminism). 2. context-free, regular. 3. False. 4. computation path. 5. False (it is uncountable).
Q: Design a DFA over Σ = {0, 1} that accepts all strings ending in "01."
A: Three states: q₀ (start, no progress), q₁ (last symbol was 0), q₂ (last two symbols were 01, accepting). On 0: q₀→q₁, q₁→q₁, q₂→q₁. On 1: q₀→q₀, q₁→q₂, q₂→q₀.
Q: Why is {aⁿbⁿ} not a regular language?
A: A DFA has finitely many states and cannot count arbitrarily high. After reading n a's, it would need to "remember" n to verify n b's follow. For n larger than the number of states, the DFA must revisit a state (pigeonhole principle), creating a loop that allows accepting strings not in the language.
Q: Give a context-free grammar for the language {aⁿbⁿ : n >= 0}.
A: S → aSb | λ.
Q: Why is the halting problem undecidable?
A: Assume a TM H decides the halting problem. Construct a TM D that runs H on its own description: if H says "halts," D loops; if H says "loops," D halts. Running D on its own description yields a contradiction, so H cannot exist.
Automata theory connects to algorithms (Chapter 3) through complexity analysis of pattern matching. Context-free grammars connect to induction (Chapter 5), since derivations are proved correct by structural induction on the parse tree. The countability argument for the halting problem uses the pigeonhole and diagonalisation ideas from counting (Chapter 6). Graphs (Chapter 10) appear as transition graphs.
deterministic finite automaton, DFA, nondeterministic finite automaton, NFA, regular language, regular expression, finite state machine, FSM, transition function, transition graph, accepting state, final state, start state, lambda transition, epsilon transition, context-free grammar, CFG, production rule, derivation, leftmost derivation, parse tree, pushdown automaton, PDA, stack, Turing machine, tape, head, halting, infinite loop, universal Turing machine, Church-Turing thesis, halting problem, undecidable, decidable, countable, uncountable, Chomsky hierarchy, language hierarchy, CS 182, Purdue, discrete math, computability, theory of computation