NPDA por aceptar el lenguaje L = {aibjckdl | i==k o j==l,i>=1,j>=1}

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final
Problema: diseñar un PDA no determinista para aceptar el lenguaje L = { : i==k o j==l, i>=1, j>=1}, es decir,

L = {abcd, aabccd, aaabcccd, abbcdd, aabbccdd, aabbbccddd, ......} 

En cada string, el número de a va seguido de cualquier número de b y el de b va seguido del número de c igual al número de a y el de c va seguido del número de d igual al número de b.

Explicación:
aquí, debemos mantener el orden de a, b, c y d. Es decir, todas las a vienen primero, luego todas las b, luego todas las c, luego todas las d. Por lo tanto, necesitamos una pila junto con el diagrama de estado. La pila mantiene el conteo de a y b. Tomaremos 2 alfabetos de pila:

 = { a, b, c, d, z } 

Donde,
= conjunto de todo el alfabeto de pila
z = símbolo de inicio de pila

Enfoque utilizado en la construcción de PDA:
en el diseño de un NPDA, para cada voluntad a’, ‘b’, ‘c’ y ‘d’ se presenta en el orden correcto.

• Para i==k: cada vez que aparezca ‘a’, empújelo en la pila y si ‘a’ vuelve a aparecer, también empújelo en la pila. Después de eso, si aparece ‘b’, no realice ninguna operación. Después de eso, cuando aparezca ‘c’, extraiga ‘a’ de la pila cada vez. Después de eso, si aparece ‘d’, no realice ninguna operación.
• Para j==l: Cada vez que aparezca ‘a’, no realice ninguna operación. Después de eso, si aparece ‘b’, empújelo en la pila y si vuelve a aparecer ‘b’, también empújelo en la pila. Después de eso, cuando aparezca ‘c’, no realice ninguna operación. Después de eso, si aparece ‘d’, extraiga ‘b’ de la pila cada vez.

De modo que la pila se vacía. Si la pila está vacía, podemos decir que la PDA acepta la string.

Funciones de transición de pila –

(q0, a, z)  (q1, az)
(q0, a, z)  (q3, z)
(q1, a, a)  (q1, aa)
(q1, b, a)  (q1, a)
(q1, c, a)  (q2, ) 
(q2, c, a)  (q2, ) 
(q2, d,  )  (q2, ) 
(q2, , z)  (qf1, z)   
(q3 a, z)  (q3, z)
(q3 b, z)  (q3, bz)
(q3 b, b)  (q3, bb)
(q3 c, b)  (q3, b)
(q3, d, b)  (q4, ) 
(q4, d, b)  (q4, ) 
(q4, , z)  (qf2, z)   

Donde, q0 = Estado inicial
qf1, qf2 = Estado final
= indica operación emergente

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje L ={ : i==k o j==l, i>=1, j>=1}.