Construir autómatas pushdown para L = {0n1m2(n+m) | m, n ≥ 0}

Requisito previo: autómatas pushdown , NPDA para aceptar el lenguaje L = {a ^m b ⁿ c ^(m+n) | m,n ≥ 1}
PDA juega un papel muy importante en la tarea de diseño del compilador. Por eso es necesario tener una buena práctica en PDA. Nuestro objetivo es construir una PDA que acepte una string de la forma {(0^n)(1^m)(2^(n+m))}

Ejemplo-

Input: 00001112222222
Output: Accepted

Input: 00011112222
Output: Not Accepted 

Enfoque utilizado en esta PDA:
puede haber cuatro casos mientras se procesa la string de entrada dada.

Caso 1- m=0: En este caso, la string de entrada tendrá la forma {0 ⁿ 2 ⁿ }. En esta condición, siga presionando 0 en la pila hasta que nos encontremos con 2. Al recibir 2, verifique si la parte superior de la pila es 0, luego sáquelo de la pila. Continúe sacando 0 hasta que se procesen todos los 2 de la string. Si llegamos al final de la string de entrada y la pila se vacía, entonces llegamos al estado final, es decir, acepta la string de entrada; de lo contrario, se mueve al estado muerto.

Caso 2- n=0: En este caso la string de entrada será de la forma {1 ^m 2 ^m }. En esta condición, siga presionando 1 en la pila hasta que nos encontremos con 2. Al recibir 2, verifique si la parte superior de la pila es 1, luego sáquelo de la pila. Continúe extrayendo 1 hasta que se procesen todos los 2 de la string. Si llegamos al final de la string de entrada y la pila se vacía, entonces llegamos al estado final, es decir, acepta la string de entrada; de lo contrario, se mueve al estado muerto.

Caso 3- m, n>0: En este caso la string de entrada será de la forma {0 ⁿ 1 ^m 2 ^(n+m) }. En esta condición, siga presionando 0 y 1 en la pila hasta que nos encontremos con 2. Al recibir 2, verifique si la parte superior de la pila es 1 o 0, luego sáquelo (1 o 0) de la pila. Continúe sacando 1 o 0 hasta que se procesen todos los 2 de la string de entrada. Si llegamos al final de la string de entrada y la pila se vacía, entonces alcanzamos el estado final, es decir, aceptamos la string de entrada; de lo contrario, pasamos al estado muerto.

Caso 4- m=0, n=0: En este caso, la string de entrada estará vacía. Por lo tanto salta directamente al estado final.