NPDA por aceptar el lenguaje L = {wwR | w ∈ (a,b)*}

Problema: Diseñe un PDA no determinista que acepte el lenguaje L = {wwR w ∈ (a, b) ⁺ }, es decir, 

L = {aa, bb, abba, aabbaa, abaaba, ......} 

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

Explicación: en este tipo de string de entrada, una entrada tiene más de un estado de transición, por lo que se denomina PDA no determinista y la string de entrada contiene cualquier orden de ‘a’ y ‘b’. Cada alfabeto de entrada tiene más de una posibilidad de pasar al siguiente estado. Y finalmente, cuando la pila está vacía, el NPDA acepta la string. En este NPDA usamos algunos símbolos que se dan a continuación: 

Γ = { a, b, z }

Donde, Γ = conjunto de todo el alfabeto de pila 
z = símbolo de inicio  de pila
a = alfabeto de entrada 
b = alfabeto de entrada 

El enfoque utilizado en la construcción de PDA –

Como queremos diseñar un NPDA, por lo tanto, cada vez que aparece ‘a’ o ‘b’, se empuja a la pila o se pasa al siguiente estado. Depende de una string. Cuando vemos el alfabeto de entrada que es igual a la parte superior de la pila, esa operación emergente de tiempo se aplica en la pila y pasa al siguiente paso. 
Entonces, al final, si la pila se vacía, podemos decir que la PDA acepta la string. 

Función de transición STACK 

(q0, a, z)  (q0, az)(q0, a, a)  (q0, aa)(q0, b, z)  (q0, bz)(q0, b, b)  (q0, bb)(q0, a, b)  (q0, ab)(q0, b, a)  (q0, ba)(q0, a, a)  (q1, ∈)(q0, b, b)  (q1, ∈)(q1, a, a)  (q1, ∈)(q1, b, b)  (q1, ∈)(q1, ∈, z)  (qf, z)

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

Entonces, este es nuestro PDA no determinista requerido para aceptar el lenguaje L = {wwR w ∈ (a, b)*} 

Ejemplo: 

Tomaremos una string de entrada: «abbbba». 

• Escanear string de izquierda a derecha
• La primera entrada es ‘a’ y sigue la regla:
• en la entrada ‘a’ y STACK alfabeto Z, empuje las dos ‘a’s en STACK como: (a, Z/aZ) y el estado será q0
• en la entrada ‘b’ y el alfabeto STACK ‘a’, empuje la ‘b’ en STACK como: (b, a/ba) y el estado será q0
• en la entrada ‘b’ y el alfabeto STACK ‘b’, empuje la ‘b’ en STACK como: (b, b/bb) y el estado será q0
• en la entrada ‘b’ y el alfabeto STACK ‘b’ (el estado es q1), saque una ‘b’ de STACK como: (b, b/∈) y el estado será q1
• en la entrada ‘b’ y el alfabeto STACK ‘b’ (el estado es q1), saque una ‘b’ de STACK como: (b, b/∈) y el estado será q1
• en la entrada ‘a’ y el alfabeto ‘a’ de la PILA y el estado q1, extraiga una ‘a’ de la PILA como: (a, a/∈) y el estado seguirá siendo q1
• en la entrada ∈ y STACK alfabeto Z, vaya al estado final (qf) como: (∈, Z/Z)

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

NOTA: Esta DPDA no aceptará el idioma vacío .

Problema: 

Diseñe un PDA determinista que acepte el lenguaje L = { wcwR w ∈ (a, b)*}, es decir, 

{aca, bcb, abcba, abacaba, aacaa, bbcbb, .......}

En cada string, la substring que está presente en el lado izquierdo de c es el reverso de la substring que está en el lado derecho actual de c. 

Explicación: 

Aquí necesitamos mantener la string de tal manera que la substring que está presente en el lado izquierdo de c sea exactamente la substring inversa que está en el lado derecho de c. Para hacer esto usamos una pila. En la string ‘a’ y ‘b’ están presentes en cualquier orden y ‘c’ vienen solo una vez. Cuando aparece ‘c’, la operación pop se inicia en la pila. Y cuando una pila está vacía, se acepta el idioma. 

Γ = {a, b, z} 

Donde, Γ = conjunto de todo el alfabeto de pila 
z = símbolo de inicio  de pila
a = alfabeto de entrada 
b = alfabeto de entrada 

El enfoque utilizado en la construcción de PDA: 

Como queremos diseñar PDA, cada vez que aparece ‘a’ o ‘b’ empujamos la pila y permanecemos en el mismo estado q0. Y cuando llega ‘c’, nos movemos al siguiente estado q1 sin empujar ‘c’ a la pila. Y después, cuando llega una entrada que es la misma que la parte superior de la pila, sale de la pila y permanece en el mismo estado. La operación POP se realiza hasta que finaliza la string de entrada. Finalmente, cuando la entrada sea ∈, pase al estado final qf. 
Cuando si la pila se vacía, se acepta el idioma. 

Donde, q0 = Estado inicial 
qf = Estado final 
z = símbolo de inicio de pila 
∈= indica operación emergente 

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, ab)(q0, b, a)  (q0, ba)(q0, c, a)  (q1, a)(q0, c, b)  (q1, b)(q1, a, a)  (q1, ∈)(q1, b, b)  (q1, ∈) (q1, ∈, z)  (qf, z) 

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

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

L = { wcwR w ∈ (a, b)*}