Construir autómatas pushdown para L = {0n1m2m3n | m, n ≥ 0}

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por el estado final
autómatas pushdown (PDA) juega un papel importante en el diseño del compilador. Por lo tanto, es necesario tener buenas manos en PDA. Nuestro objetivo es construir un PDA para L = {0 ⁿ 1 ^m 2 ^m 3 ⁿ | m, n ≥ 0}

Ejemplos –

Input : 00011112222333
Output : Accepted

Input : 0001122233
Output : Not Accepted

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

• Caso-1: m = 0 – En este caso, la string de entrada tendrá la forma {0 ⁿ 3 ⁿ }. En esta condición, siga presionando 0 en la pila hasta que nos encontremos con 3. Al recibir 3, verifique si la parte superior de la pila es 0, luego sáquelo (0) de la pila. Extraiga 0 hasta que se procesen todos los 3 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-2: n = 0: en este caso, la string de entrada tendrá 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 (1) de la pila. Continúe en pop 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 alcanzamos el estado final, es decir, aceptamos la string de entrada; de lo contrario, pasamos al estado muerto.
• Caso-3: m, n>0: en este caso, la string de entrada tendrá la forma {0 ⁿ 1 ^m 2 ^m 3 ⁿ }. 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, luego sáquelo (1) de la pila. Continúe en pop 1 hasta que se procesen todos los 2 de la string de entrada. Luego, al recibir 3, verifique si la parte superior de la pila es 0, luego sáquelo (0) de la pila. Extraiga 0 hasta que se procesen todos los 3 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.

Los autómatas pushdown finales para el idioma dado son: