ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 54d83fb7
In formal language theory, a Pushdown Automaton with two stacks (2-stack PDA) is computationally equivalent to a Turing Machine because:
In formal language theory, a Pushdown Automaton with two stacks (2-stack PDA) is computationally equivalent to a Turing Machine because:
Multiple Choice Options
- A
One stack acts as the input and the other as output
- B✓ Correct Option
Two stacks can simulate the left and right sides of a Turing machine tape
- C
Both stacks only support FIFO operations
- D
None of the mentioned
Detailed Technical Solution & Explanation
A 2-stack PDA can simulate an infinite two-way tape of a Turing Machine: one stack holds tape contents to the left of the head, and the other stack holds tape contents under and to the right of the head. Moving left pops from stack 1 and pushes to stack 2; moving right does the reverse.
Option Analysis:
•
Option A (One stack acts as the input and the o...): Does not explain Turing completeness.
•
Option B (Two stacks can simulate the left and ...): Correct. Two LIFO stacks completely emulate an infinite bidirectional tape.
•
Option C (Both stacks only support FIFO operations): Stacks are LIFO (Last-In, First-Out), not FIFO.
•
Option D (None of the mentioned): Incorrect since B is the foundational proof.
Reference: Mock Test 02NEC Licensure Syllabus