Construir autómatas pushdown para palíndromos de todas las longitudes

Un autómata pushdown (PDA) es como un autómata finito no determinista (NFA) épsilon con una pila infinita. PDA es una forma de implementar lenguajes libres de contexto. Por lo tanto, es importante aprender a dibujar PDA.

Aquí, tomemos el ejemplo de un palíndromo de longitud impar:
Que-1: Construya un PDA para el lenguaje L = {wcw’ | w={0, 1}*} donde w’ es el reverso de w.

Enfoque utilizado en este PDA:
siga presionando 0 y 1 sin importar lo que esté en la parte superior de la pila hasta llegar al elemento central. Cuando se escanea el elemento central ‘c’, procéselo sin realizar ningún cambio en la pila. Ahora, si el símbolo escaneado es ‘1’ y la parte superior de la pila también contiene ‘1’, extraiga el elemento de la parte superior de la pila o si el símbolo escaneado es ‘0’ y la parte superior de la pila también contiene ‘0’, extraiga el elemento de la parte superior de la pila . Si la string se vacía o el símbolo escaneado es ‘$’ y la pila se vacía, entonces llegue al estado final; de lo contrario, muévase al estado muerto.

• Paso 1: al recibir 0 o 1, sigue empujándolo en la parte superior de la pila sin pasar al siguiente estado.
• Paso 2: al recibir un elemento ‘c’, pasa al siguiente estado sin realizar ningún cambio en la pila.
• Paso 3: al recibir un elemento, verifique si el símbolo escaneado es ‘1’ y la parte superior de la pila también contiene ‘1’ o si el símbolo escaneado es ‘0’ y la parte superior de la pila también contiene ‘0’, luego extraiga el elemento de la parte superior de la pila de lo contrario, pasar al estado muerto. Siga repitiendo el paso 3 hasta que la string se vacíe.
• Paso 4: Verifique si el símbolo escaneado es ‘$’ y la pila no contiene ningún elemento, luego muévase al estado final; de lo contrario, muévase al estado inactivo.

Ejemplos:

Input : 1 0 1 0 1 0 1 0 1
Output :ACCEPTED

Input : 1 0 1 0 1 1 1 1 0
Output :NOT ACCEPTED

Ahora, tomemos el ejemplo del palíndromo de longitud uniforme:
Que-2: Construya un PDA para el lenguaje L = {ww’ | w={0, 1}*} donde w’ es el reverso de w.

Enfoque utilizado en este PDA:
para la construcción de palíndromos de longitud uniforme, el usuario debe utilizar autómatas de empuje no deterministas (NPDA). Un NPDA es básicamente un NFA con una pila añadida.
El NPDA para este idioma es idéntico al anterior excepto por la transición épsilon. Sin embargo, hay una diferencia significativa, que esta PDA debe adivinar cuándo dejar de presionar símbolos, saltar al estado final y comenzar a emparejar fuera de la pila. Por lo tanto, esta máquina es decididamente no determinista.
Siga presionando 0 y 1 sin importar lo que esté en la parte superior de la pila y, al mismo tiempo, controle la string de entrada, ya sea que llegue a la segunda mitad de la string de entrada o no. Si llega al último elemento de la primera mitad de la string de entrada, luego de procesar el último elemento de la primera mitad de la string de entrada, haga un movimiento épsilon y pase al siguiente estado. Ahora, si el símbolo escaneado es ‘1’ y la parte superior de la pila también contiene ‘1’, extraiga el elemento de la parte superior de la pila o si el símbolo escaneado es ‘0’ y la parte superior de la pila también contiene ‘0’, extraiga el elemento de la parte superior de la pila . Si la string se vacía o el símbolo escaneado es ‘$’ y la pila se vacía, entonces llegue al estado final; de lo contrario, muévase al estado muerto.

• Paso 1: al recibir 0 o 1, siga empujándolo en la parte superior de la pila y, al mismo tiempo, siga comprobando si llega a la segunda mitad de la string de entrada o no.
• Paso 2: si llega al último elemento de la primera mitad de la string de entrada, empuje ese elemento en la parte superior de la pila y luego haga que un épsilon se mueva al siguiente estado.
• Paso 3: al recibir un elemento, verifique si el símbolo escaneado es ‘1’ y la parte superior de la pila también contiene ‘1’ o si el símbolo escaneado es ‘0’ y la parte superior de la pila también contiene ‘0’, luego extraiga el elemento de la parte superior de la pila de lo contrario, pasar al estado muerto. Siga repitiendo el paso 3 hasta que la string se vacíe.
• Paso 4: Verifique si el símbolo escaneado es ‘$’ y la pila no contiene ningún elemento, luego muévase al estado final; de lo contrario, muévase al estado inactivo.

Ejemplos:

Input : 1 0 0 1 1 1 1 0 0 1
Output :ACCEPTED

Input : 1 0 0 1 1 1
Output :NOT ACCEPTED

Ahora, tomemos el ejemplo del palíndromo de longitud total, es decir, un PDA que puede aceptar palíndromos de longitud impar y palíndromo de longitud par:
Que-3: Construya un PDA para el lenguaje L = {ww’ | wcw’, w={0, 1}*} donde w’ es el reverso de w.

Enfoque utilizado en este PDA:
para la construcción de palíndromos de todas las longitudes, el usuario debe utilizar NPDA.
El enfoque es similar al ejemplo anterior, excepto que ahora, junto con el movimiento épsilon, ahora el usuario debe mostrar un movimiento de transición más del símbolo ‘c’, es decir, si la string tiene una longitud impar y si llega al elemento central ‘c’, simplemente procéselo y muévalo. al siguiente estado sin hacer ningún cambio en la pila.

• Paso 1: al recibir 0 o 1, siga empujándolo en la parte superior de la pila y, al mismo tiempo, siga comprobando si la string de entrada tiene la misma longitud, entonces si llega a la segunda mitad de la string de entrada o no, sin embargo, si la string de entrada es de longitud impar, entonces siga comprobando si llega al elemento medio o no.
• Paso 2: si la string de entrada tiene una longitud uniforme y llega al último elemento de la primera mitad de la string de entrada, empuje ese elemento en la parte superior de la pila y luego haga que un épsilon se mueva al siguiente estado o si la string de entrada tiene una longitud impar, entonces en al recibir un elemento ‘c’, pasar al siguiente estado sin realizar ningún cambio en la pila.
• Paso 3: al recibir un elemento, verifique si el símbolo escaneado es ‘1’ y la parte superior de la pila también contiene ‘1’ o si el símbolo escaneado es ‘0’ y la parte superior de la pila también contiene ‘0’, luego extraiga el elemento de la parte superior de la pila de lo contrario, pasar al estado muerto. Siga repitiendo el paso 3 hasta que la string se vacíe.
• Paso 4: Verifique si el símbolo escaneado es ‘$’ y la pila no contiene ningún elemento, luego muévase al estado final; de lo contrario, muévase al estado inactivo.

Ejemplos:

Input : 1 1 0 0 1 1 1 1 0 0 1 1
Output :ACCEPTED

Input : 1 0 1 0 1 0 1
Output :ACCEPTED