Introducción de autómatas pushdown – Part 1

Ya hemos discutido los autómatas finitos . Pero los autómatas finitos se pueden usar para aceptar solo lenguajes regulares. 
Pushdown Automata es un autómata finito con memoria adicional llamada pila que ayuda a los autómatas Pushdown a reconocer lenguajes libres de contexto. 
  
Un Pushdown Automata (PDA) se puede definir como: 

• Q es el conjunto de estados
• ∑ es el conjunto de símbolos de entrada
• Γ es el conjunto de símbolos pushdown (que se pueden empujar y sacar de la pila)
• q0 es el estado inicial
• Z es el símbolo pushdown inicial (que inicialmente está presente en la pila)
• F es el conjunto de estados finales
• δ es una función de transición que transforma Q x {Σ ∪ ∈} x Γ en Q x Γ*. En un estado dado, la PDA leerá el símbolo de entrada y el símbolo de la pila (parte superior de la pila) y pasará a un nuevo estado y cambiará el símbolo de la pila.

 Descripción instantánea (ID) 
La descripción instantánea (ID) es una notación informal de cómo un PDA «calcula» una string de entrada y toma la decisión de aceptar o rechazar la string. 

Un ID es un triple (q, w, α), donde: 
1. q es el estado actual. 
2. w es la entrada restante. 
3.α es el contenido de la pila, arriba a la izquierda. 
   
La notación 
de torniquete ⊢ se denomina «notación de torniquete» y representa 
un movimiento. 
El signo ⊢* representa una secuencia de movimientos. 
Por ejemplo, (p, b, T) ⊢ (q, w, α) 
Esto implica que mientras se realiza una transición del estado p al estado q, el símbolo de entrada ‘b’ se consume, y la parte superior de la pila ‘T’ es reemplazado por una nueva string ‘α’ 

 Ejemplo: Definir los autómatas pushdown para lenguaje {a ⁿ b ⁿ | n > 0} 
Solución: M = donde Q = { q0, q1 } y Σ = { a, b } y Γ = { A, Z } y δ está dado por: 

δ( q0, a, Z ) = { ( q0, AZ ) } 
δ( q0, a, A) = { ( q0, AA ) } 
δ( q0, b, A) = { ( q1, ∈) } 
δ( q1, b, A) = { ( q1, ∈) } 
δ( q1, ∈, Z) = { ( q1, ∈) } 
  
Veamos cómo funciona este autómata para aaabbb. 
 

Explicación: Inicialmente, el estado de los autómatas es q0 y el símbolo en la pila es Z y la entrada es aaabbb como se muestra en la fila 1. Al leer ‘a’ (que se muestra en negrita en la fila 2), el estado seguirá siendo q0 y empujará símbolo A en la pila. En la siguiente ‘a’ (que se muestra en la fila 3), empujará otro símbolo A en la pila. Después de leer 3 a, la pila será AAAZ con A en la parte superior. Después de leer ‘b’ (como se muestra en la fila 5), ​​aparecerá A y se moverá al estado q1 y la pila será AAZ. Cuando se lean todas las b, el estado será q1 y la pila será Z. En la fila 8, en el símbolo de entrada ‘∈’ y Z en la pila, aparecerá Z y la pila estará vacía. Este tipo de aceptación se conoce como aceptación por pila vacía. 

Diagrama de estado de autómatas de empuje hacia abajo:

  
Nota :  

• El autómata pushdown anterior es de naturaleza determinista porque solo hay un movimiento desde un estado en un símbolo de entrada y un símbolo de pila.
• Los autómatas pushdown no deterministas pueden tener más de un movimiento desde un estado en un símbolo de entrada y un símbolo de pila.
• No siempre es posible convertir autómatas pushdown no deterministas en autómatas pushdown deterministas.
• El poder expresivo del PDA no determinista es más en comparación con el PDA determinista expresivo, ya que NPDA acepta algunos lenguajes pero no el PDA determinista, que se discutirá en el próximo artículo.
• Los autómatas pushdown pueden implementarse utilizando la aceptación por pila vacía o la aceptación por estado final y uno puede convertirse en otro.

  
Pregunta: ¿Cuáles de los siguientes pares tienen DIFERENTE poder expresivo? 

A. Autómatas finitos deterministas (DFA) y autómatas finitos no deterministas (NFA) 
B. Autómatas de empuje hacia abajo deterministas (DPDA) y autómatas de empuje hacia abajo no deterministas (NPDA) 
C. Máquina de Turing de cinta única determinista y máquina de Turing de cinta única no determinista máquina de Turing de cinta 
D. Máquina de Turing de una sola cinta y máquina de Turing de varias cintas 

Solución: cada NFA se puede convertir en DFA. Entonces, el poder expresivo es el mismo. Como se discutió anteriormente, cada NPDA no se puede convertir a DPDA. Entonces, el poder de NPDA y DPDA no es el mismo. Por lo tanto, la opción (B) es correcta.