[Math] Pushdown automata for the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$

automatacontext-free-grammar

I'm trying to make a PDA that accepts the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$ by empty stack. (Here $w^\text{R}$ denotes the reverse of the string $w$.) Our stack symbol s $\#$.

I've come up with this so far, but I don't know how to handle the $001$ in the middle of $w$ and $w^\text{r}$. Any suggestions?

  1. Start by pushing $0,1$ onto the stack: $(q_0,0,\#) \rightarrow (q_0,0\#)$ and $(q_0,1,\#) \rightarrow (q_0, 1\#)$

  2. Continue to push $0,1$ onto stack: $(q_0,0,0) \rightarrow (q_0,00)$, $(q_0,0,1) \rightarrow (q_0, 01)$, $(q_0,1,0) \rightarrow (q_0,10)$, $(q_0,1,1) \rightarrow (q0, 11)$

  3. Handle $001$ and transition to $q_1$: I don't know how to do this

  4. Pop $0,1$ off stack: $(q_1,0,0) \rightarrow (q_1,E)$, $(q_1,1,1) \rightarrow (q_1,E)$

If stack is empty after this point, than accept language.

Best Answer

The basic idea is to use the non-determinism of the PDA to "guess" where the middle $\mathtt{001}$ is, and don't push/pop anything to/from the stack while reading this guess. The rest of the PDA will be similar to the usual PDA to recognise the language $L_0 = \{ ww^\text{R} : w \in \{\mathtt{0},\mathtt{1} \}^* \}$ by empty stack. The main point is that if you guess wrong you just need to ensure that the stack doesn't empty at the end of the computation (or that the computation doesn't continue to the end of the string).

In broad outline, I would design the PDA as follows (assuming that $\#$ is pushed onto the stack before the computation begins):

  1. Begin reading the input string symbol by symbol (ignoring the top of the stack), and pushing the corresponding symbol onto the stack (without popping anything).
  2. Using a $\varepsilon;\varepsilon\to\varepsilon$ transition, guess where the middle $\mathtt{001}$ is.
  3. Ensure that the next three symbols are $\mathtt{001}$ (but don't alter the stack).
  4. Continue reading the input string symbol by symbol, but now ensure that the symbol being read is the same as the symbol at the top of the stack (and pop that symbol off the stack).
  5. If the stack symbol $\#$ appears at the top of the stack, pop it off the stack and move to a new state without any further instructions.
Related Question