edited by
12,188 views
66 votes
66 votes

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?

  1. $L(P)$ is necessarily $Σ^*$ but $N(P)$ is not necessarily $Σ^*$.
  2. $N(P)$ is necessarily $Σ^*$ but $L(P)$ is not necessarily $Σ^*$.
  3. Both $L(P)$ and $N(P)$ are necessarily $Σ^*$.
  4. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$
edited by

5 Answers

Best answer
60 votes
60 votes

Answer is (D).

In NPDA we may have a dead configuration. This mean we may not give any transition to any alphabet from this state.

We say that a string is accepted if PDA is in final state after reading the final symbol in the string or after it has read '$' symbol denoting end of the string and it is in final state.

Now coming to options:

Question never says that we have transitions defined for all the alphabet symbols in the PDA. Although it is ALREADY in the FINAL state we may not have ANY transition for any input symbol. In this case string will be rejected as it will never finish reading the string.

To sum up: A string is rejected in following two ways:

  1. If no transition is defined for any configuration(this includes the final state as well because to accept the string we need the transition $(f,\$,\_)\to (f,_)$ in final state or accepting state where blank $('\_')$ denotes arbitrary stack symbol that does not matter because we are not accepting by EMPTY stack
  2. If string enters a configuration for which no transition is defined, STRING is rejected.

So, option (D) is correct. Because the same way it may not empty the stack when it finishes reading the string.

edited by
8 votes
8 votes
Since its NPDA.. So we cannot have any transitions over any alphabet. So it should be d neither L(p) and N(p) is sigma star.
4 votes
4 votes

In Each option it is saying "necessarily", so if you can find any one instance of both which cannot accept (sigma)* is sufficient for rejecting the given option.

One such instances is :

acceptance by empty stack : only pushing symbol is defined ( so stack will never be empty) and hence it cannot accept (sigma)*

acceptance by final state :- if any transition are not defined over sigma, pda will halt and not accept the string.

 

Hence, it is not necessarily that the given pda will accept (sigma)*.

–5 votes
–5 votes
I think (C) will be the answer

because emptying stack and accept a language both are same
Answer:

Related questions