The language accepted by a pushdown automaton whose stack is limited to 10…
2002
The language accepted by a pushdown automaton whose stack is limited to 10 items is best described as:
- A.
Context-free
- B.
Regular
- C.
Deterministic context-free
- D.
Recursive
Attempted by 10 students.
Show answer & explanation
Correct answer: B
A PDA normally gets extra power from an unbounded stack. If the stack is limited to at most 10 items, then the number of possible stack contents is finite. Combining the PDA control state with these finitely many stack configurations gives an equivalent finite automaton. Therefore, such a machine can recognize only regular languages, and every language it accepts is regular.