NPDA por aceptar el lenguaje L = {am bn cp dq | m+n=p+q; m,n,p,q>=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 = { | m + n = p + q : m, n, p, q>=1}, es decir,

L = {abcd, abbcdd, abbccd, abbbccdd, ......}

En cada string, el número total de ‘a’ y ‘b’ es igual al número total de ‘c’ y ‘d’.

Explicación –
Aquí, necesitamos mantener el orden de ‘a’, ‘b’, ‘c’ y ‘d’. Por lo tanto, necesitamos una pila junto con el diagrama de estado. La pila mantiene el recuento de ‘a’, ‘b’, ‘c’ y ‘d’. Tomaremos 2 alfabetos de pila:

 = { 1, z } 

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

Enfoque utilizado en la construcción de PDA:
como queremos diseñar un NPDA, cada vez que ‘a’, ‘b’, ‘c’ y ‘d’ aparecerán en el orden correcto. Cuando aparezcan ‘a’ y ‘b’, empujaremos ‘1’ a la pila. Después de eso, cuando aparezcan ‘c’ y ‘d’, saque ‘1’ de la pila cada vez. Entonces, al final, si la pila se vacía, podemos decir que la PDA acepta la string.

Funciones de transición de pila –

(q0, a, z)  (q0, 1z)
(q0, a, 1)  (q0, 11)
(q0, b, 1)  (q1, 11)
(q1, b, 1)  (q1, 11)
(q1, c, 1)  (q2, )
(q2, c, 1)  (q2, )
(q2, d, 1)  (q3, )
(q3, d, 1)  (q3, )
(q3, , z)  (qf, z)     
        

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

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje L = { | metro + norte = pag + q ; m, n, p, q>=1}.