I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then nondeterministically guess "$01$" in $w$, however I am stuck with the rest. I understand the condition $i/3=j/2$, but how do I make my PDA accept that? Does it have to be nondeterministic too? How do I approach this?


For the "$w$ part", as you said (or implied) yourself, you don't need the stack at all. After switching to the "$0^i1^j$ part", in some state $s_2$, you can put for the $0$'s in the input alternatingly first an $a$ on the stack, then delete it with a $b$ for the second $0$, then add a $c$ for the third $0$, then start over. By adding only two of the three symbols for each stream of three zeros (as you delete $a$), you get $2/3i$ symbols in the stack which is just equal to $j$. You get a stack like this: $kbcbc\ldots$ ($k$ being the bottom stack symbol).

Now, you just have to delete each $b$ or $c$ with the ones coming on the input tape and accept iff you reach the bottom of the stack ($k$) when the input is complete.

The second part of the PDA might look something like this ($\lambda$ being the empty word):

$(s_2, 0, k) \rightarrow (s_2, ak)$

$(s_2, 0, a) \rightarrow (s_2, b)$

$(s_2, 0, b) \rightarrow (s_2, cb)$

$(s_2, 0, c) \rightarrow (s_2, ac)$

$(s_2, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, b) \rightarrow (s_3, \lambda)$

$(s_3, \lambda, k) \rightarrow (s_e, k)$

| cite | improve this answer | |
  • $\begingroup$ Check out my answer! $\endgroup$ – Pavel Dec 23 '14 at 14:27
  • $\begingroup$ You don't need to put several symbols on the stack as my solution shows. Btw. you should rethink the title of your question as it does not really have much to do with non-determinism (and also is not at all specific). $\endgroup$ – lukas.coenig Dec 23 '14 at 14:39
  • $\begingroup$ Regarding your answer: I am not quite familiar with your notation, but I suppose, this: (q2, 1, 000, (q2, 0)) is intended to mean: in state q2, when reading 1 and 000 are the three topmost stack symbols, go into state q2 and put 0 on the stack. This you can't do. You can only read the one single top-most symbol on the stack. $\endgroup$ – lukas.coenig Dec 23 '14 at 14:52
  • $\begingroup$ Your solution won't work for me, because I can only use ones and zeros, and no k, a, b or c, the alphabet of my PDA = {0,1} (not counting the bottom marker). And regarding the "000" you're right, however, I used "000" because I didn't wanna create an extra state responsible for deleting 3 symbols, I can change that if you want. However I can PUT 000 on the stack. $\endgroup$ – Pavel Dec 23 '14 at 14:59
  • $\begingroup$ With PDAs, you have separate alphabets for the input and the stack. Using a, b, c as stack symbols is perfectly fine! k is what I called the bottom symbol which is z0 in your attempt. $\endgroup$ – lukas.coenig Dec 23 '14 at 15:01

I have thought about this about realized that the solution is the following:

1) read w how i described 2) as you read 0, put 000 on the stack, and then as you read 1, remove 00 from the stack, and that's how you get the correct PDA.

So, the PDA is the following(z0 is the bottom marker):

(q0, 0, z0, (q0, z0))

(q0, 1, z0, (q0, z0))

(q0, 0, z0, (q1, z0)) // non-deterministically guess that the next 2 symbols are "01"

(q1, 1, z0, (q2, z0)) // accept "01"

(q2, 0, z0, (q2, 000z0)) // put 000 when we see the bottom marker

(q2, 0, 0, (q2, 0000)) // put 000 on top of the other zeros

(q2, 1, 000, (q2, 0)) // remove 00, here I omitted the extra state responsible for deleting 3 symbols at once and wrote it as "the PDA is seeing "000""

(q3, lamda, (q3, z0)) // stop

Really sucks that I always overlook the little parts in formal definitions of things, I didn't know that the string that I could put on the stack could be of any length and not just 1 symbol.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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