# Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$

$$L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$$ This was an exercise from our workbook, but their solution is a bit different

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. We'd prefer you ask about a specific conceptual issue you're uncertain about. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Jun 9, 2022 at 14:56

First of all your language is DCFL so there exist at least one DPDA for your language but you made NPDA because at state $$q_0$$ ,$$\delta(q_0,0,A)\neq\emptyset$$ and $$\delta(q_0,\epsilon,A)\neq\emptyset$$ makes your diagram NPDA by the formal definition of DPDA.

$$Case:1$$

If $$i =0$$ and $$j\neq 0$$, then the condition $$i+j>0$$ is satisfied. In this case language becomes $$L_1=\{1^j2^j\}.$$

Algorithm to make DPDA:

Push $$1$$'s and pop $$1$$'s against $$2$$'s.

$$Case:2$$

If $$j =0$$ and $$i\neq 0$$, then the condition $$i+j>0$$ is satisfied. In this case language becomes $$L_2=\{0^i2^i\}.$$

Algorithm to make DPDA:

Push $$0$$'s and pop $$0$$'s against $$2$$'s.

$$Case:3$$

If $$i\neq 0$$ and $$j\neq 0$$, then the condition $$i+j>0$$ is satisfied. In this case language becomes $$L_3=\{0^i1^j2^{i+j}\}.$$

Algorithm to make DPDA:

Push $$0$$'s and $$1$$'s, and then pop $$1$$'s and $$0$$'s against $$2$$'s.

Now combining all above 3 cases your language becomes $$L=\{12,1122........,02,0022,........0122,00112222\}.$$

Final transition function for DPDA: By taking $$q_0$$ is initial state, $$Z_0$$ as stack bottom, $$q_f$$ is final state.

$$\delta(q_0,1,Z_0)=(q_0,1Z_0).$$

$$\delta(q_0,1,1)=(q_0,11).$$

$$\delta(q_0,0,Z_0)=(q_0,0Z_0).$$

$$\delta(q_0,0,0)=(q_0,00).$$

$$\delta(q_0,1,0)=(q_0,10).$$

$$\delta(q_0,2,1)=(q_1,\epsilon).$$

$$\delta(q_0,2,0)=(q_1,\epsilon).$$

$$\delta(q_1,2,0)=(q_1,\epsilon).$$

$$\delta(q_1,2,1)=(q_1,\epsilon).$$

$$\delta(q_1,\epsilon,Z_0)=(q_{f},Z_0).$$

State diagram for DPDA: All languages $$L_1, L_2$$ as well as $$L_3$$ is accepted by this DPDA. N. B:- In your question $$i$$ and $$j$$ both simultaneously are not $$0$$ because otherwise the condition $$i+j>0$$ will be failed. The above diagram is acceptance by final state, you could make the diagram acceptance by empty stack(left for you which is your homework).