New answers tagged

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