Let P be a non-deterministic push-down automaton (NPDA) with exactly one…
2005
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be Σ. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?
- A.
L(P) is necessarily Σ* but N(P) is not necessarily Σ*
- B.
N(P) is necessarily Σ* but L(P) is not necessarily Σ*
- C.
Both L(P) and N(P) are necessarily Σ*
- D.
Neither L(P) nor N(P) are necessarily Σ*
Attempted by 12 students.
Show answer & explanation
Correct answer: D
The NPDA has only one state q, which is both the start and accepting state. The stack starts with Z and can only contain Z due to the single symbol in the stack alphabet. For L(P), acceptance occurs by being in state q after reading an input string, but since no transitions are defined, only strings that do not require any stack operations may be accepted. For N(P), acceptance requires the stack to be empty after reading a string, which can only happen if there are transitions that pop Z. Without any transition definitions, neither language is guaranteed to be Σ*. Therefore, the correct answer is D.