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

Requisito previo: autómatas pushdown , NPDA para aceptar el lenguaje L = {a ^m b ^(n+m) c ^m | m, n >= 1}
Problema: Construir autómatas pushdown para L = {0 ^m 1 ^(n+m) 2 ⁿ | m, n ≥ 0}

Ejemplo:

Input: 011122
Output: Accepted

Input: 00000112222
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 será de la forma {1 ⁿ 2 ⁿ }. 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 2- n=0:
En este caso, la string de entrada tendrá la forma {0 ^m 1 ^m }. En esta condición, siga presionando 0 en la pila hasta que nos encontremos con 1. Al recibir 1, 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 1 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 ^m 1 ^(m+n) 2 ⁿ }. En esta condición, siga presionando 0 en la pila hasta que nos encontremos con 1. Al recibir 1, verifique si la parte superior de la pila es 0 y luego sáquelo de la pila. Continúe sacando 0 hasta que todos los 0 desaparezcan y la pila quede vacía. Después de eso, 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 y luego sáquelo de la pila. Continúe extrayendo 1 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 llegue al estado final, es decir, acepte la string de entrada; de lo contrario, muévase 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.

Diagrama de transición de estado: