NPDA por aceptar el lenguaje L = {am b(2m) | m>=1}

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

Problema: diseñe un PDA no determinista para aceptar el lenguaje L = { [Tex]b^{2m} [/Tex]: m>=1}, es decir,

L = {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ......} 

En cada una de las strings, el número de a es seguido por el doble de b. 

Explicación: aquí, debemos mantener el orden de a y b. Es decir, todas las a vienen primero y luego todas las b. Por lo tanto, necesitamos una pila junto con el diagrama de estado. La pila mantiene el recuento de a y b. Aquí, el número de b es exactamente el doble del número de a. 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. Después de eso, cuando aparezca la ‘b’, saque una ‘a’ de la pila. Pero hacemos esta operación de estallido para la posición alternativa de las b, es decir, para dos b, sacamos una ‘a’ y para cuatro b, sacamos dos ‘a’. 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)[ Indicates no operation only state change ](q0, b, a)  (q1, a) [ Indicates pop operation for alternate 'b'] (q1, b, a)  (q2, ) [ Indicates no operation only state change ] (q2, b, a)  (q1, a) [ Indicates pop operation for alternate 'b'] (q1, b, 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^{2m} [/Tex]: m>=1}.