New answers tagged pushdown-automata
1
Suppose that your PDA is reading $011$.
At the beginning, the PDA is at state $q_1$, and the stack is empty. The only move the PDA can make is to put $\$$ on the stack and to transition to state $q_2$.
Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q_2$ which puts $0$ on the stack. The input is now $11$, ...
-1
A PDA (including a NPDA) can only move if there is a symbol on the top of the stack, the possible moves depend on the current state, the symbol on the top of the stack and the input symbol (or $\epsilon$). No stack, no further moves possible.
1
Hint 1: $L = L_1 \cup L_2$ for some $L_1$ and $L_2$ which are obviously context-free.
Hint 2:
1
Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.
1
In the answer by @LukeMathieson it is proved, that non-deterministic two-stack pushdown automaton is as powerful as Turing Machine. A stronger statement is also true:
Deterministic two-stack pushdown automaton is as powerful as Turing Machine
Proof:
Because it is known that deterministic queue automaton is equivalent to Turing machine all we need is to ...
Top 50 recent answers are included
