# Tag Info

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.