# Pushdown Automata

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 ∑*

## Related questions

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
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$