Q. The language accepted by a Pushdown Automation in which the stack is…
2003
Q. The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as
- A.
Context Free
- B.
Regular
- C.
Deterministic Context Free
- D.
Recursive
Attempted by 171 students.
Show answer & explanation
Correct answer: B
Answer: Regular
Reason: A pushdown automaton with its stack limited to 10 items has only a finite number of possible stack contents. When you combine this finite stack-space with the machine's finite control, the overall number of configurations becomes finite, so the machine can be simulated by a finite automaton.
Finite number of stacks: If the stack alphabet has s symbols, the number of possible stacks of depth up to 10 is finite (sum of s^i for i = 0..10).
Finite configurations imply an equivalent finite automaton: each combination of control state and stack content can be treated as a distinct finite-state.
Conclusion: The languages accepted by such a bounded-stack PDA are regular.
Example: The language { a^n b^n : n ≤ 10 } is a finite union of finite languages and therefore regular. An unbounded language like { a^n b^n : n ≥ 0 } would require an unbounded stack and is not covered by the bounded-stack PDA.
A video solution is available for this question — log in and enroll to watch it.