NPDA por aceptar el lenguaje L = {anbm | n,m ≥ 1 y n ≠ m}

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 , es decir,

L = {aab, abb, aaab, abbb, aaaab, aaabb, aabbb, abbbb ......} 

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

Explicación –
Aquí, necesitamos 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 }

Dónde,

= set of all the stack alphabet
z = 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’. 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 cada vez. Entonces, al final, si la pila se vacía y b está llegando o la string finaliza y la pila no está vacía, entonces 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, , a)  (qf, a)   
(q1, b, z)  (qf, z)   

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

Diagrama de transición de estado –

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje .