Past exam question: 2082 Chaitra (Regular), Q10(a)
Open in the Padhaiko appQuestion
How working of TM different from PDA?
Solution
Comparative Architectural and Operational Differences: The fundamental differences between a Turing Machine (TM) and a Pushdown Automaton (PDA) are:
- Memory Storage & Access: A PDA has a restricted Last-In-First-Out (LIFO) stack where only the top symbol can be read or modified. A TM has an infinite, two-way tape providing unrestricted random read/write access to any cell.
- Tape Head Movement: A PDA's input head moves only in one direction (left-to-right) and consumes input. A TM's tape head can move both Left () and Right () or remain Stationary ().
- Computational Power: A PDA recognizes Context-Free Languages (CFLs). A TM recognizes Recursively Enumerable (RE) languages and computes general partial recursive functions (Church–Turing Thesis).
- Halting Behavior: A PDA always finishes reading its input in bounded steps; a TM may accept, reject, or loop indefinitely.
Answer:
A PDA has a restricted one-way input head and a LIFO stack. A TM has an infinite two-way tape with random read/write access and bidirectional head movement, making it strictly more powerful (accepting recursively enumerable languages vs. context-free languages).