Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.
share|cite|improve this answer

simple ... the string is W001Wr right ? where Wr is the reverse of W... eg if w=001 then Wr=100 right? sol: (q0,1,Zo)=(q0,1z0)// same for 0; (q0,1,0)=(q0,10)// same for 0,1; (q0,1,0)=(q1,e) // same for 0; sme in the q1 state... pop at same values.. in the end u left with 001 string in stack ... and the simply pop them at new state :)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.