Construir autómatas pushdown para L = {0(n+m)1m2n | metro, norte ≥ 0}

Requisito previo: autómatas pushdown

Problema: Construir autómatas Pushdown para L = {0 ^(n+m) 1 ^m 2 ⁿ | metro, norte ≥ 0}

PDA similares-

• Esta PDA parece ser similar a la PDA de S2 = {0 ^m 1 ^(n+m) 2 ⁿ } pero la producción es diferente. S2 producirá una salida que no tiene 1 igual a la suma de 0 y 2, mientras que S1 no.
• Esta PDA parece ser similar a la PDA del lenguaje L2 = {a ^m b ^(n+m) c ⁿ | m,n > 1} pero L2 no contiene ninguna producción de longitud 0, 1, 2, 3. Si bien esta PDA aceptará la string vacía, la string de longitud 1, 2, 3 además de la string aceptada por la PDA de lenguaje L2.

Ejemplo-

Input: NULL String
Output: Accepted

Input: 0000011122
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 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 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 ^(n+m) 1 ^m 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 agregando 0 hasta que se procesen todos los 1 de la string de entrada. Después de eso, al recibir 2, verifique si la parte superior de la pila es 0 y luego sáquelo de la pila. Continúe sacando 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 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: