NPDA por aceptar el lenguaje L = {a(m+n)bmcn | m, n ≥ 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 idioma.  Las strings del idioma dado serán:

L = {aabc, aaabcc, aaabbc, aaaabbcc, ......} 

En cada una de las strings, la suma total del número de ‘b’ y ‘c’ es igual al número de ‘a’. Y todas las c vienen después de ‘a’ y ‘b’. 

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

 = { a, 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’ viene antes de ‘b’ y ‘b’ viene antes de ‘c’. Primero tenemos que contar el número de a y ese número debe ser igual al número de b. Cuando todas las b hayan terminado, cuente el número de a y eso debería ser igual al número de c. Para todos los ‘a’, empujaremos ‘a’ en la pila cada vez y luego comenzaremos a sacarlos cuando lleguen ‘b’. Después de terminar de sacar las ‘b’ y después de que lleguen las ‘c’, sacaremos estas ‘a’ 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, az)(q0, a, a)  (q0, aa)(q0, b, a)  (q1, )(q1, b, a)  (q1, )(q1, c, a)  (q2, )(q2, c, a)  (q2, )(q2,,  z)  (qf, z)

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

Diagrama de transición de estado

 Nota: Este idioma es similar al idioma 

*** QuickLaTeX cannot compile formula:
 

*** Error message:
Error: Nothing to show, formula is empty

, pero usamos  en lugar de  .