I'm having some trouble with the following language:

$L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

with alphabet $A=\{0,1,2,3\}$

I'd like to find a deterministic pushdown automata to recognise it according to the empty stack criterion.

I built the deterministic pushdown automata according to the final states criterion and as the language has the prefix property there should be an automata according to the empty stack criterion.

Is there an algorithm to do this? The one I use to translate from one criterion to the other doesn't not seem to work for deterministic automata.

  • $\begingroup$ "... doesn't not seem to work ..." - I'm having a hard time understanding that. Do you have an extra "not" there? Also, if you mean that it doesn't seem to work, can you edit the question to show us what you tried? What algorithm did you use, what was the result, and why do you think it doesn't work? Without knowing what approach you took, it's hard to provide meaningful feedback on that. $\endgroup$ – D.W. Jan 23 '16 at 2:03

DPDA for $\mathcal L=\{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

let's try to understand wich words the automata should accept:

$\{\varepsilon,03,13,23,0033,1133,2233,0133,0233,1233,000333,111333,\dots \}\in \mathcal L$

So we can see the "two parts" of the automata, the first part will contain the $0,1,2$ digits and the second part of the automata will contain the $3$ digits, so for the first part we will do a "push" for some $X$ and for the second part we will do a "pop" for $X$, we will accept the word if the stack is empty so in the end we will do a "pop" for some $Z$ that have been in the stack alaready

Try this one, if it is not $100\%$ at least it will lead you to bulid it by yourself


enter image description here

| cite | improve this answer | |
  • $\begingroup$ @Rodrigo what do you mean by "moves with empty stack" $\endgroup$ – user45087 Jan 23 '16 at 7:04
  • $\begingroup$ $\delta(q_0,\lambda, Z)=\{(q_0,\lambda)\}\neq\{(q_0,\lambda),(q_1,XZ)\}$ what is this $(q_1,XZ)$ ? $\endgroup$ – user45087 Jan 23 '16 at 13:24
  • $\begingroup$ This doesn't look right to me, looks like it accepts $020333$. $\endgroup$ – G. Bach Jan 23 '16 at 14:03
  • $\begingroup$ @G.Bach Yes, I edited but the idea is same $\endgroup$ – user45087 Jan 23 '16 at 14:28

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.