Introducción a Pushdown Automata

Estructura básica de PDA

Un autómata pushdown es una forma de implementar una gramática libre de contexto de una manera similar a la que diseñamos DFA para una gramática regular. Un DFA puede recordar una cantidad finita de información, pero un PDA puede recordar una cantidad infinita de información.

Básicamente, un autómata pushdown es -

"Finite state machine" + "a stack"

Un autómata de empuje tiene tres componentes:

  • una cinta de entrada,
  • una unidad de control, y
  • una pila de tamaño infinito.

El cabezal de la pila escanea el símbolo superior de la pila.

Una pila hace dos operaciones:

  • Push - se agrega un nuevo símbolo en la parte superior.

  • Pop - se lee y se elimina el símbolo superior.

Una PDA puede leer o no un símbolo de entrada, pero tiene que leer la parte superior de la pila en cada transición.

Una PDA se puede describir formalmente como una tupla de 7 (Q, ∑, S, δ, q 0 , I, F) -

  • Q es el número finito de estados

  • ∑ es el alfabeto de entrada

  • S son símbolos de pila

  • δ es la función de transición: Q × (∑ ∪ {ε}) × S × Q × S *

  • q0es el estado inicial (q 0 ∈ Q)

  • I es el símbolo inicial de la parte superior de la pila (I ∈ S)

  • F es un conjunto de estados de aceptación (F ∈ Q)

El siguiente diagrama muestra una transición en un PDA de un estado q 1 al estado q 2 , etiquetado como a, b → c -

Esto significa en el estado q1, si encontramos una cadena de entrada ‘a’ y el símbolo superior de la pila es ‘b’, luego hacemos estallar ‘b’, empujar ‘c’ en la parte superior de la pila y pasar al estado q2.

Terminologías relacionadas con PDA

Descripción instantánea

La descripción instantánea (ID) de un PDA está representada por un triplete (q, w, s) donde

  • q es el estado

  • w es entrada no consumida

  • s es el contenido de la pila

Notación de torniquete

La notación "torniquete" se utiliza para conectar pares de ID que representan uno o varios movimientos de una PDA. El proceso de transición se indica con el símbolo del torniquete "⊢".

Considere un PDA (Q, ∑, S, δ, q 0 , I, F). Una transición se puede representar matemáticamente mediante la siguiente notación de torniquete:

(p, aw, Tβ) ⊢ (q, w, αb)

Esto implica que mientras se hace una transición de estado p a estado q, el símbolo de entrada ‘a’ se consume, y la parte superior de la pila ‘T’ es reemplazado por una nueva cadena ‘α’.

Note - Si queremos cero o más movimientos de una PDA, tenemos que usar el símbolo (⊢ *) para ello.