PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q10(a)

Theory of Computation · 1 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

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:

  1. 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.
  2. 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 ().
  3. 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).
  4. 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).

All past exam questions for Theory of Computation