NPDA por aceptar el lenguaje L = {ambncn | 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 lenguaje  , es decir,

L = {abc, aabc, aabbcc, abbbccc, aabbbccc ...... } 

El siguiente DFA debe contener:

1. El número de a es igual al número de c.
2. El número de b es independiente del número de a y c.
3. Se debe mantener el orden de a, b y c.

Explicación: El orden de a, b y c se mantiene de la siguiente manera, es decir, primero vienen todas las a, luego vienen todas las b y luego las c. Dado que el número de b es exactamente igual al número de c, entonces, la pila mantendrá el recuento de b y c. La pila utilizada tendrá un símbolo de inicio y un símbolo adicional para el conteo de b y c.

 = { 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 –

• Paso 1: Cada vez que aparezca ‘a’, empújelo en la pila y si vuelve a aparecer ‘a’, empújelo también.
• Paso 2: cuando aparezca la ‘c’, saque una ‘a’ de la pila cada vez.
• Paso 3: cuando aparezca ‘b’, ignórelo y cambie el estado en el diagrama de estado.
• Paso 4: detenga la ejecución si al final, la pila se vacía. Por lo tanto, la PDA acepta la string.

Nótese que siempre se mantiene el orden de a, b y c. 

Funciones de transición de pila:

(q0, a, z)  (q0, z)(q0, b, z)  (q1, bz)(q1, b, b)  (q1, bb)(q1, c, b)  (q2, )(q2, c, b)  (q2, )(q2, , z)  (qf, z)

Diagrama de transición de estado:  

Aquí, q0 = Estado inicial qf = Estado final  = indica operación pop Y, q1,q2= Estado intermedio