582 views
0 votes
0 votes

The following question is a modified version of this question https://gateoverflow.in/3785/gate2005-it-38, in this GATE question they have NPDA, but I'm asking about DPDA

Let D be a deterministic push-down automaton (DPDA) 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 DPDA. The stack is initialized with one Z before the start of the operation of the DPDA. Let the input alphabet of the DPDA be Σ. Let L(P) be the language accepted by the DPDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the DPDA 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 Σ*.

1 Answer

0 votes
0 votes
Option 1 is correct.

L(P) is necessarily Σ* as initial state is final state and null move is not needed for acceptance by final state.

but N(P) is not necessarily Σ* because language Σ* has prefix property which will make symbol move and null move both necessary.

Related questions

8 votes
8 votes
3 answers
1
1 votes
1 votes
0 answers
2
Matrix asked Jul 28, 2018
1,548 views
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
3 votes
3 votes
1 answer
3
AskHerOut asked Oct 22, 2017
746 views
1) Can a Deterministic PDA has two epsilon transition each reading different Stack symbol to perform a transition?2) Can a transition be performed without reading Stack s...
2 votes
2 votes
2 answers
4