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

Question

Could someone please help me check if my automaton is correctly designed?

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

Answer 1

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.

Your language has 3 cases:

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