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 $\Sigma$. 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?
-
$L(P)$ is necessarily $\Sigma*$ but $N(P)$ is not necessarily $\Sigma*$.
-
$N(P)$ is necessarily $\Sigma*$ but $L(P)$ is not necessarily $\Sigma*$.
- Both $L(P)$ and $N(P)$ are necessarily $\Sigma*$.
- Neither $L(P)$ nor $N(P)$ are necessarily $\Sigma*$.
According to me both the languages should be equivalent and so accordingly both $L(P)$ and $N(P)$ are necessarily $\Sigma*$.
Best Answer
HINT: What if $\delta$, the transition relation (or transition function, if that’s how your PDAs are defined), is empty?