NPDA para L = {0i1j2k | i==j o j==k ; yo, j, k >= 1}

Requisito previo – Autómatas pushdown , aceptación de autómatas pushdown por estado final
El lenguaje L = {0 ⁱ 1 ^j 2 ^k | i==j o j==k ; i , j , k >= 1} dice que cada string de ‘0’, ‘1’ y ‘2’ tiene cierto número de 0, luego cierto número de 1 y luego cierto número de 2. La condición es que el recuento de cada uno de estos 3 símbolos sea al menos 1. Dos condiciones importantes para este lenguaje son que el recuento de 0 debe ser igual al recuento de 1 O el recuento de 1 debe ser igual al recuento de 2. Suponga que la string termina con ‘$’.

Ejemplos:

Input: 0 0 0 1 1 1 2 2 2 2 2  
        Here 0's = 3, 1's  = 3 so i = j, 2's = 5 
Output: Accepted 
          
Input: 0 0 1 1 1 2 2 2
        Here 0's = 2, 1's = 3, 2's = 3 so j = k
Output: Accepted

Input : 0 0 1 1 1 2 2 2 2
        Here 0's = 2, 1's = 3, 2's = 4 
Output: Not accepted 

Hay 2 enfoques para la solución. El primero es para i==j y el segundo es para j==k. Estos son:

Pasos para i == j :

1. Ingrese todos los 0 en la pila
2. Cuando obtengamos 1 como entrada, extraiga un 0 de la pila y pase al siguiente estado.
3. Si la entrada es 1, extraiga 0 de la pila.
4. Si la pila se vacía (es decir, cada 0 correspondiente a un 1 se ha extraído, por lo que i = j) y la entrada es 2, ignórela y pase al siguiente estado.
5. Si la entrada es 2, ignórela. Si finaliza la entrada y se recibe $, vaya al estado final.

Pasos para j == k :

1. Ingrese todos los 0 en la pila
2. Cuando obtengamos 1 como entrada, empújelo a la pila y pase al siguiente estado.
3. Si la entrada es 1, entonces empújelo a la pila.
4. Si la entrada es 2, saque un 1 de la pila y vaya al siguiente estado.
5. Si la entrada es 2, extraiga 1 de la pila. Si finaliza la entrada y se recibe $, extraiga un 0 de la pila.
6. Extraiga todos los 0 restantes de la pila. Si la pila se vacía, vaya al estado final.