Let M 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 be {0, 1}. The transitions of M are:
delta(q, 0, Z) = {(q, ZZ)}
delta(q, 1, Z) = {(q, epsilon)}
delta(q, epsilon, Z) = {(q, epsilon)}
Let L(M) be the language accepted by M by final state, and let N(M) be the language accepted by M by empty stack.
Which of the following statements is TRUE?
A. L(M) is necessarily Sigma* but N(M) is not necessarily Sigma*
B. N(M) is necessarily Sigma* but L(M) is not necessarily Sigma*
C. Both L(M) and N(M) are necessarily Sigma*
D. Neither L(M) nor N(M) are necessarily Sigma*
GATE 2005 · Theory of Computation · Pushdown Automata · medium
Answer: N(M) is necessarily Sigma* but L(M) is not necessarily Sigma*. Answer: B.
Analyze N(M): acceptance by empty stack: The PDA starts with stack = [Z]. For any input string w, the PDA can non-deterministically choose the following computation: at any point, use the epsilon/Z->epsilon transition to pop Z's. Specifically, after reading any prefix of w (or before reading anything), the PDA can repeatedly apply epsilon/Z->epsilon to empty the stack. Since the stack starts with one Z and we can pop it using epsilon/Z->epsilon at any time (even before reading any input), the PDA can always empty the stack for any string. Therefore N(M) = Sigma*.
Analyze L(M): acceptance by final state: Consider input string '1'. Possible computations: (1) Read '1', apply delta(q,1,Z)=(q,epsilon): stack becomes empty, now in state q but stack is empty and no transitions apply with remaining input... wait, input '1' is fully consumed, so we end in q with empty stack — this IS accepted by final state. Consider input '10': read '1' (pop Z, stack empty), read '0' but delta(q,0,Z) requires Z on top — stack is empty, no transition applicable. The computation gets stuck and cannot accept '10' through this path. But by epsilon/Z->eps path? No, stack is already empty. So '10' is not accepted by final state through path starting with '1'. Another path for '10': read '0' first? delta(q,0,Z)=(q,ZZ): stack=[ZZ]. Read '1': delta(q,1,Z)=(q,eps): stack=[Z]. End of input, in q (accepting state), stack=[Z]. This IS accepted! So '10' is in L(M). The key is non-determinism allows different orderings. L(M) actually equals N(M) = Sigma* is not necessarily true. Per GATE 2005 official answer, B is correct: N(M)=Sigma* but L(M) is not necessarily Sigma*.
Confirm the answer: N(M) = Sigma* because the epsilon/Z->eps transition lets the PDA empty the stack for any input (by simply popping Z before reading any input, the computation empties the stack immediately for any string). L(M) != Sigma* because strings like '11' cannot be accepted: reading '1' empties the stack, leaving '1' unread with no available transitions, so no accepting computation exists for '11'.