NPDA por aceptar el lenguaje L = {an bm cn | m,n>=1}

Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final 

Problema – – Diseñar un PDA no determinista que acepte el lenguaje L = { [Tex]b^m [/Tex] | m, n>=1}, es decir,

 L = { abc, abbc, abbbc,  aabbcc, aaabccc, aaaabbbcccc, ...... } 

En cada una de las strings, el número de a es igual al número de c. Y el número de b es independiente del número de a y c. Este problema es bastante similar al NPDA para aceptar el lenguaje L = { [Tex]b^n [/Tex] | m, n>=1}. La única diferencia es que aquí usamos  en lugar de  . 

Explicación: aquí, debemos mantener el orden de a, b y c. Es decir, todas las a vienen primero y luego todas las b y luego las c. Por lo tanto, necesitamos una pila junto con el diagrama de estado. La pila mantiene el recuento de a y c. El número de a es exactamente igual al número de 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’. Cuando aparezca ‘a’, empújelo en la pila y si vuelve a aparecer ‘a’, también empújelo. Y, cuando aparezca ‘c’, extraiga una ‘a’ de la pila cada vez. Y para ‘b’, no haremos nada en la pila, solo cambiaremos el estado en el diagrama de estado. 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, a)(q1, b, a)  (q1, a)(q1, c, a)  (q2,  )(q2, c, a)  (q2,  )(q2, , z)  (qf, z )        

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

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje L = {  [Tex]b^m [/Tex] | m, n>=1}.