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

  1. A.

    Context Free

  2. B.

    Regular

  3. C.

    Deterministic Context Free

  4. 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.

Explore the full course: Gate Guidance By Sanchit Sir