Unit 3: Pushdown automata and Turing machines
Theory of Computation notes · PTU syllabus (PGCA1927)
On this page
- Unit summary
- Ambiguity and parse trees
- Pushdown automata
- Equivalence of PDAs and CFGs; non-deterministic PDAs
- Standard Turing machines
- Turing machine construction for simple problems
- Variations of Turing machines
- The universal Turing machine and the Church–Turing thesis
- Recursive, recursively enumerable and context-sensitive languages
- Key terms
- Quick revision
- Important questions
Unit summary
Adding memory to automata increases their power, from pushdown automata to Turing machines. This unit covers ambiguity and parse trees, pushdown automata and their equivalence with CFGs, non-deterministic PDAs, standard Turing machines and variations, universal Turing machines, the Church–Turing thesis, recursive and recursively enumerable languages, context-sensitive languages, the Chomsky hierarchy and constructing Turing machines.
After this unit you can
- Identify ambiguous grammars
- Design pushdown automata and relate them to CFGs
- Design Turing machines and explain their variations and the universal machine
- Distinguish recursive, recursively enumerable and context-sensitive languages
PTU syllabus topics
- Ambiguity
- parse trees
- equivalence of PDAs
- non-deterministic PDA
- standard Turing machines and variations
- universal Turing machines
- Church-Turing thesis
- recursive and recursively enumerable languages
- context-sensitive languages
- Chomsky hierarchy
- TM construction for simple problems
Rule shapes
A → BC or A → a
A → a followed by variables
Use
CYK parsing algorithm
Top-down parsing, PDA construction
Derivation length
2n − 1 steps for a string of length n
n steps
Topic 1
Ambiguity and parse trees
- A grammar is ambiguous if some string has two different parse trees (or two leftmost derivations).
Example
E → E + E, E × E or id: "id + id × id" has two parse trees — one grouping (id + id) × id. Rewriting with precedence (E → E + T, T → T × F) removes the ambiguity.
- Some CFLs are inherently ambiguous — every grammar for them is ambiguous, e.g., {aⁱbʲcᵏ : i = j or j = k}.
Topic 2
Pushdown automata
- A PDA is a finite automaton with a stack: a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F). Each move reads an input symbol (or ε), pops the top stack symbol and pushes a string.
Example
PDA for {aⁿbⁿ}: on each a push A; on each b pop A; accept when the input ends and only Z0 remains. For aabb: push, push, pop, pop → accept.
- Acceptance by final state or by empty stack — equivalent in power.
Topic 3
Equivalence of PDAs and CFGs; non-deterministic PDAs
- For every CFG there is a PDA accepting its language, and every PDA's language is context-free — PDAs recognise exactly the CFLs.
Moves
At most one choice in each situation
Several possible moves
Power
Deterministic CFLs only
All CFLs
Example
{wcwᴿ} (marked palindromes)
{wwᴿ} (even palindromes) needs guessing the middle
Use
Parsers of programming languages (LR parsing)
Theory
- Unlike finite automata, non-deterministic PDAs are more powerful than deterministic ones.
Topic 4
Standard Turing machines
- A Turing machine has a finite control, an infinite tape and a read–write head that moves left or right: 7-tuple (Q, Σ, Γ, δ, q0, B, F), with δ(q, X) = (p, Y, L or R).
- 1Replace the leftmost 0 by X
- 2Move right to the leftmost 1 and replace it by Y
- 3Move left back to the leftmost remaining 0
- 4Repeat
- 5If no 0s remain and no 1s remain beyond the Ys, accept; otherwise reject
Topic 5
Turing machine construction for simple problems
Example
Unary addition 111 0 11 → 11111: move right to the 0, change it to 1, move to the end, change the last 1 to blank, halt. The machine computes 3 + 2 = 5.
- Other exercises: binary increment, copying a string, checking palindromes, computing n mod 2.
Topic 6
Variations of Turing machines
- Multi-tape TM
- Several tapes and heads — same power, faster (polynomially)
- Non-deterministic TM
- Several possible moves — same power
- Multi-head and two-way infinite tape
- Same power
- Enumerators
- Print strings of a language — same as recognisers
- Linear bounded automaton
- Tape limited to the input length — accepts context-sensitive languages
- All reasonable variants recognise the same class of languages, supporting the robustness of the model.
Topic 7
The universal Turing machine and the Church–Turing thesis
- A universal Turing machine U takes the encoding of any TM M and an input w and simulates M on w — the theoretical model of a stored-program computer.
- Church–Turing thesis: every function that is effectively computable by an algorithm can be computed by a Turing machine. It is a thesis, not a theorem, supported by the equivalence of many models (lambda calculus, recursive functions, register machines).
Topic 8
Recursive, recursively enumerable and context-sensitive languages
Recursive (decidable)
TM that always halts
Answers yes or no for every input
Recursively enumerable (semi-decidable)
TM that halts on members
May loop forever on non-members
Context-sensitive
Linear bounded automata
Decidable; e.g., {aⁿbⁿcⁿ}
- Recursive languages are closed under complement; if both L and its complement are r.e., L is recursive.
- Regular
Finite automata
- Context-free
Pushdown automata
- Context-sensitive
Linear bounded automata
- Recursively enumerable
Turing machines
Key terms
- Ambiguous grammar
- Grammar giving two parse trees for some string
- Pushdown automaton
- Finite automaton with a stack
- Turing machine
- Finite control with an infinite read–write tape
- Universal Turing machine
- TM simulating any other TM from its description
- Recursively enumerable language
- Language accepted by some TM
Quick revision
- Ambiguity; removing it with precedence; inherent ambiguity.
- PDA 7-tuple; acceptance by final state or empty stack; PDA ⇔ CFG; DPDA weaker than NPDA.
- TM 7-tuple; constructing TMs; variants equal in power; LBAs.
- Universal TM; Church–Turing thesis.
- Recursive vs r.e.; context-sensitive; full Chomsky hierarchy.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.When is a grammar ambiguous?
- Q2.Design the idea of a PDA for {aⁿbⁿ}.
- Q3.Are DPDAs as powerful as NPDAs?
- Q4.Define a Turing machine.
- Q5.State the Church–Turing thesis.
- Q6.Distinguish recursive and recursively enumerable languages.
Long-answer questions
- Q1.Explain ambiguity with an example and how to remove it.
- Q2.Design a PDA for a given language and explain PDA–CFG equivalence.
- Q3.Design a Turing machine for {0ⁿ1ⁿ} and explain TM variations.
- Q4.Explain the universal TM, Church–Turing thesis and the Chomsky hierarchy.
Stuck on this unit?
Message SBS on WhatsApp for help with Theory of Computation, or to ask about studying M.Sc IT at Synetic.