NPDA para el lenguaje L ={w∈ {a,b}*| w contiene igual no. de a y b}

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 ={w?{a,b}* | w contiene igual no. de a’s y b’s}, es decir,

L = {ab, aabb, abba, aababb, bbabaa, baaababb, .......}

El número de a y b es el mismo en todas las strings.

Explicación –
Aquí, no necesitamos mantener ningún orden de a y b. Por lo tanto, nuestro diagrama de estado contendrá solo un estado inicial y un estado final. La pila mantiene el recuento de a y b. Tomaremos 3 alfabetos de pila:

 = {a, b, z}

Donde, = conjunto de todo el alfabeto de pila
z = símbolo de inicio de pila

Enfoque utilizado en la construcción de PDA:
si ‘a’ viene primero, empújelo en la pila y si vuelve a aparecer ‘a’, también empújelo. De manera similar, si ‘b’ viene primero (‘a’ aún no viene), entonces empújelo a la pila y si vuelve a aparecer ‘b’, también empújelo.

Ahora, si ‘a’ está presente en la parte superior de la pila y viene ‘b’, saque la ‘a’ de la pila. Y si ‘b’ está presente en la parte superior de la pila y aparece ‘a’, saque la ‘b’ de la pila.

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, z)    (q0, bz)
(q0, b, b)    (q0, bb)
(q0, a, b)    (q0, )
(q0, b, a)    (q0, )
(q0, , z)    (qf, z)

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

So, this is our required non deterministic PDA for accepting the strings which contain equal no. of a’s and b’s.
Example:We will take one input string: “aabbba” PDA accept or not?.
solution:
1.Scan string from left to right.
2.on input ‘a’ and STACK alphabet Z, push the ‘a’s into STACK as : (a,Z/aZ) and state will be q0.
3.second input ‘a’ and STACK alphabet ‘a’, push the ‘a’s into STACK as : (a,a/aa) and state will be q0.
4.Third input ‘b’ and STACK alphabet ‘a’, pop from STACK as : (b,a/∈) and state will be q0.
5.on input ‘b’ and STACK alphabet ‘a’, pop from STACK as : (b,a/∈) and state will be q0.
6.on input ‘b’and STACK alphabet Z, push the ‘b’s into STACK as : (b,Z/bZ) and state will be q0.
7.on input ‘a’ and STACK alphabet ‘b’, pop from STACK as : (a,b/∈) and state will be q0.
8.on input ∈ and STACK alphabet Z, go to final state(qf) as : (∈, Z/Z).

Entonces, al final, la pila se vacía, entonces podemos decir que la PDA acepta la string.