Aptitude Overflow
+9 votes
982 views

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 Σ*
asked in Theory of Computation by (19.4k points)  
edited by | 982 views

4 Answers

+15 votes
Best answer

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 symol. 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,$,_)---> (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.

 

answered by (7.2k points)  
selected by
If transitions defined each and every symbol...in that case what is the ans??
@Gabbar then A will be the ans.

If transitions defined each and every symbol from E(sigma) then for any string it will process it fully and it will end at final state. //Accepted E *

But for empty stack mechanism it may not accept E* there is possibility that transitions defined each and every symbol but still it is not making stack empty.
@rajesh tell  me here only one state is given in question which is q then after this how could u say "But for empty stack mechanism it may not accept E* there is possibility that transitions defined each and every symbol but still it is not making stack empty" plz give the example for it
@Rajesh

" for empty stack mechanism it may not accept E* there is possibility that transitions defined each and every symbol but still it is not making stack empty"

What is that scenario?

I mean if every symbol is defined, then why couldnot stack be empty?

is it one of dead state configuration u mean?

@srestha @ Rajesh 

I think even if all transitions on alphabets are defined then still it may not guarantee  Σ*. e.g we have specified that if (q,a,b)->(q,ab) but we have not specified (q,a,a) then it will be trapped in dead configuration.Still option is d.

@akb115

 e.g we have specified that if (q,a,b)->(q,ab) but we have not specified (q,a,a)

in context of PDA, transition consist of a tupple (q,a,t).... if we say transition on alphabet 'a', it means every possible tupple (q,a,ti), (where ti is diiferent possiblities of top of stack for particular q and a) should be present...

Thank you, I got it. So in that scenario answer would be A???
yes..
+1 vote
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.
answered by (2.1k points)  
NPDA cannot have transitions over any alphabet?
@arjun sir I mean to say we have choice of transitions in nondetrministic machine..so since first state is also a final state so if it don't have any transition.so it can accept epsilon
That's true. But epsilon being accepted is necessary for L to be Σ* rt?

@sonu: You are correct. NPDA can have dead configurations and in that case string is always rejected.

is acceptance by final state possible with exactly one state?
will the answer change if NPDA is changed to PDA?? Because just like NPDA deterministic PDA need not have transitions defined for every state and it also have dead configuration??
–2 votes
I feel c is the correct answer..
answered by (13k points)  
Why? How can we be sure that PDA will empty its stack?
–2 votes
I think (C) will be the answer

because emptying stack and accept a language both are same
answered by (55.5k points)  
srry, but question is not about that .......
Because $\Sigma$ could be anything

not always $\Sigma ^*$

rt?

Related questions

2,455 questions
849 answers
346 comments
15,474 users