Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to make a PDA that accepts the language w001(rev w) | w = {0,1}* by empty stack, where rev w means the reverse of w. (Stack symbol = #)

I've come up with this so far, but I don't know how to handle the 001 in the middle of w and rev w. Any suggestions?

  1. Initial Start: Push 0,1 onto stack

    (q0,0,#) -> (q0,0#), (q0,1,#) -> (q0, 1#)

  2. Continue to push 0,1 onto stack

    (q0,0,0) -> (q0,00), (q0,0,1) -> (q0, 01), (q0,1,0) -> (q0,10), (q0,1,1) -> (q0, 11)

  3. Handle 001 and transition to q1

    Don't know how to do this

  4. Pop 0,1 off stack

    (q1,0,0) -> (q1,E), (q1,1,1) -> (q1,E)

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Hint: Non-deterministically guess where the middle 001 is, and don't push or pop anything when reading this substring. (If you guess wrong, just make sure the stack doesn't empty at the end of the computation.)

share|improve this answer
What if you have a string like 0011011100 which should not be accepted by the PDA because the middle substring is 01 instead of 001. If you epsilon transition right before 01, read 0 and 1 without pushing or popping, and then transition to my 4th step, wouldn't that string be accepted by the PDA? –  Takkun Oct 3 '12 at 19:36
@Takkun: When I say "guess where the middle 001 is" I mean that the PDA non-deterministically enters a subroutine of two parts: the first expects that the next three symbols read off the tape are 001, and the second expects that whatever comes after this 001 is the reverse of whatever occurred before it. If either of these conditions fails (for whatever reason) you need to do something to ensure that the stack is not empty at the end of the computation. If both conditions are satisfied, the stack should naturally empty at the end of the computation. –  Arthur Fischer Oct 3 '12 at 19:55

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|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.