Let P be a non-deterministic push-down automaton (NPDA) with exactly one…
GATE · 2005 · IT
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 43 students.
Sign up free to check your answer
Sign up freeLoading lesson…