search
Log In
0 votes
52 views

Let P be a non-deterministic pushdown 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 S. 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 statement 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) is necessarily ∑*

  4. Neither L(P) nor N(P) are necessarily ∑*

in Theory of Computation 52 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
60 views
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it
asked Jan 16, 2019 in Theory of Computation anonymous 60 views
0 votes
0 answers
2
215 views
Options: $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \} \cup \left \{ b^{n} | n\geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}\right )^{m}a | n,m \geq 0 \right \}$ $NONE$
asked Dec 10, 2018 in Theory of Computation jatin khachane 1 215 views
0 votes
2 answers
3
197 views
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
asked Oct 25, 2018 in Theory of Computation Shamim Ahmed 197 views
0 votes
0 answers
4
...