Autómatas Push-Down

Un Aceptor Push-Down (APD) es una tupla de 6 elementos $M=(Q,S,U,P,I,F)$ con:

1. $Q$: conjunto finito de estados.
2. $S$: alfabeto finito de entrada.
3. $U$: alfabeto finito de pila o stack.
4. $P$: es el programa de $M$. Es una secuencia finita de instrucciones.
5. $I\subseteq Q$: conjunto de estados iniciales.
6. $F\subseteq Q$: conjunto de estados finales.

En cada instrucción el estado $q$ es la etiqueta o rótulo de la instrucción y $q^{\prime }$ es el estado sucesor. Cada $q$ en $Q$ rotula un único tipo de instrucción (scan, write, o read). Se considera una tupla $(q,\phi ,\sigma )$ con $q\in Q,\phi \in S^{\ast },\sigma \in U^{\ast })$ la configuración de $M$. Una configuración describe el estado total de un APD en algún punto de su análisis de una cinta.

Algunos conceptos:

1. $(q,\lambda ,\lambda )$ es configuración inicial $⟺q\in I$ de $M$.
2. $(q^{\prime },\omega ,\lambda )$ es configuración final $⟺q^{\prime }\in F,\omega \in S^{\ast }$ de $M$.
3. $\phi$ es string aceptado por $M$ $⟺$ $M$ tiene secuencia de movimientos $(q_i,\lambda ,\lambda )⟹(q_F,\phi ,\lambda )$, donde el stack debe estar vacío.
4. $L$ es el lenguaje reconocido $L(M)=\{\omega \in S^{\ast }/(q_i,\lambda ,\lambda )⟹(q_f,\omega ,\lambda );q_i\in I,q_f\in F\}$.
5. $M$ es determinístico $⟺$ para toda configuración nunca hay más de un movimiento posible.
6. Una instrucción $q]\text{ write}(u,q^{\prime })$ es impropia si $q^{\prime }$ es rótulo de una instrucción read.
7. Un APD es propio si su programa no contiene instrucciones impropias.

Transformación de APD a APDP

Sean los APD $M$ y APDP $M^{\prime }$: el siguiente procedimiento verifica que $L(M^{\prime })=L(M)$.

1. $\forall q,q^{\prime }$ con $(q,\phi ,\sigma )\stackrel{k\text{ writes}}{⟹}(q^{\prime \prime },\phi ,\sigma \tau )\stackrel{k\text{ reads}}{⟹}(q^{\prime },\phi ,\sigma )$ con $k\ge 1$ (1). Por cada instrucción $p]\text{ move}(-,q)$ se agrega $p\text{ move}(-,q^{\prime })$. Si $q\in I$ en $M$ $⟹q^{\prime }\in I$ en $M^{\prime }$. Esto se repite para cada par $q$ y $q^{\prime }$ para los cuales $M$ tiene una secuencia de movimientos como (1).
2. Se borran todas las instrucciones impropias. Las restantes forman el $P$ de $M^{\prime }$.

Tabla: Construcción de un Analizador Push-Down

Dada $G=(N,T,P_G,\Sigma )$ se puede construir un $M=(Q,T,U,P_M,I,F)$. Sean $U=N\cup T\cup \{\Sigma \}$, $Q=\{q_I,w_R\}\cup \{q_X/x\in U\}$, $I=\{q_I\}$, $q_R\in F$.

Acción	Condición	Instrucción
Para inicializar:		$q_{\downarrow }$] write $(\Sigma ,q_R)$
Para expandir:	$\forall A\to \psi \in G$ $\{\begin{array}{l}A\in N\cup \{\Sigma \}\\ \psi \in (N\cup T{)}^{\ast }-\lambda \end{array}$	$q_R$] read $(A,q_A)$ $q_A$] write $({\psi }^R,q_R)$
Para hacer “matching”:	$\forall t\in T$	$q_R$] read $(t,q_{\downarrow })$ $q_{\downarrow }$] scan $(t,q_R)$
Para aceptar $\lambda$:	Si $\Sigma \to \lambda \in G$	$q_{\downarrow }\in F$

Por cada GLC $G$ se puede construir un APD $M$ tal que $L(M)=L(G)$.