NPDA por aceptar el lenguaje L = {amb(2m+1) | metro ≥ 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 ≥ 1}, o,L = { | m ≥ 1}, es decir,

L = {abbb, aabbbbb, aaabbbbbbb, aaaabbbbbbbbb, ......}

En cada una de las strings, el número de ‘b’ es uno más que el doble del número de ‘a’. 

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. Tomaremos 2 alfabetos de pila:

 = { a, z }Where,  = set of all the stack alphabetz = stack start symbol

Enfoque utilizado en la construcción de PDA: como queremos diseñar un NPDA, cada vez que ‘a’ viene antes de ‘b’. Introduciremos una ‘a’ en la pila por cada ‘a’ y de nuevo para la siguiente ‘a’, introduciremos una ‘a’ en la pila. Y luego, cuando llegue ‘b’, para la primera ‘b’ no haremos nada, solo cambiará el estado. Para las próximas dos ‘b’, sacaremos una ‘a’ y nuevamente para las próximas dos ‘b’, sacaremos una ‘a’. Y de manera similar realizamos esto alternativamente. es decir, para la tercera ‘b’ sacamos la primera ‘a’ Para la quinta ‘b’ sacamos la segunda ‘a’ Para la séptima ‘b’ sacamos la tercera ‘a’ Entonces, al final, si la pila se vacía, entonces podemos decir que la string es aceptada por el PDA. 

Funciones de transición de pila –

(q0, a, z) (q0, az)        (q0, a, a) (q0, aa)     (q0, b, a) (q1, a)  [ Indicates no operation only state change ](q1, b, a) (q2, a)  [ Indicates no operation only state change ](q2, b, a) (q3,  )  [Indicates pop operation ](q3, b, a) (q2, a )  [ Indicates no operation only state change ](q3, , z) (qf, z )    

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