Siguiente: Autómatas de pila y Un nivel arriba: Autómatas de pila Anterior: Principios básicos

Reconocimiento de lenguajes

Sea $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ un autómata de pila. Una descripción instantánea (DI) es una cadena

$$q\sigma;\tau\in Q\times\mbox{\it Ent\/}^*\times\mbox{\it AlfP\/}^*$$

que indica que el autómata está en el estado q, se está leyendo el primer símbolo a la izquierda de $\sigma$ y $\tau$ es el contenido de la pila. El símbolo en el tope de la pila es el primero de $\tau$. Diremos que una DI $d_1=q^1\sigma^1;\tau^1$ se sigue de otra $d_0=q^0\sigma^0;Y^0\tau^0$, $\mbox{\it AutP\/}\vdash (d_0\rightarrow d_1)$, si es el resultado de aplicar la transición correspondiente a d₀. Formalmente, $\mbox{\it AutP\/}\vdash (d_0\rightarrow d_1)$ si y sólo si

$$\begin{array}{lcl} \left[\sigma^0=e^0\sigma^1\right]\land\le... ...\/})\in\mbox{\it tran\/}(q^0,\mbox{\it nil\/},Y^0) \end{array}$$

La cerradura reflexivo-transitiva de la relación ``se sigue'' es la relación ``se deriva'', denotada como $\mbox{\it AutP\/}\vdash (d_0\stackrel{*}{\rightarrow} d_1)$. La descripción inicial de una palabra $\sigma \in \mbox{\it Ent\/}^*$ es $\mbox{\it DI\/}_0(\sigma)\equiv\left[q_0\sigma;X\right]$. Una DI $d=q\sigma;\tau$ se dice

• final si $q\in F$ y $\sigma=\mbox{\it nil\/}$, es decir, si indica que se está en un estado final y no quedan símbolos de entrada,
• de pila vacía si $\tau=\mbox{\it nil\/}$, es decir, en el tope de la pila no hay símbolo alguno.

Una palabra $\sigma \in \mbox{\it Ent\/}^*$ se dice

• reconocida por estados finales si desde la descripción inicial de ella se arriba a una final, es decir, si
  
  $$\exists q\in F,\tau\in\mbox{\it AlfP\/}^*:\ \mbox{\it AutP\/}... .../}_0(\sigma)\stackrel{*}{\rightarrow} q.\mbox{\it nil\/};\tau).$$
  
  

• reconocida por pila vacía si desde la descripción inicial de ella se arriba a una de pila vacía, es decir, si
  
  $$\exists q\in Q:\ \mbox{\it AutP\/}\vdash (\mbox{\it DI\/}_0(\... ...\stackrel{*}{\rightarrow} q.\mbox{\it nil\/};\mbox{\it nil\/}).$$
  
  

Sea $\mbox{\it LF\/}(\mbox{\it AutP\/})$ el lenguaje consistente de las palabras reconocidas por estados finales. Sea $\mbox{\it LPV\/}(\mbox{\it AutP\/})$ el lenguaje consistente de las palabras reconocidas por pila vacía. Ambas nociones de reconocimiento son equivalentes.

Lema 2.1   Para cada autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ existe otro autómata de pila $\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$ tal que el lenguaje reconocido por estados finales en el primer autómata es reconocido por pila vacía en el segundo, es decir

$$\mbox{\it LF\/}(\mbox{\it AutP\/})=\mbox{\it LPV\/}(\mbox{\it AutP\/})'$$

En efecto, $\mbox{\it AutP\/}'$ se construye a partir de $\mbox{\it AutP\/}$ como sigue:

1.

en general, actúese en $\mbox{\it AutP\/}'$ como se hace en $\mbox{\it AutP\/}$,

2.

cuando se llegue a un estado final de $\mbox{\it AutP\/}$, transítese en $\mbox{\it AutP\/}'$ de manera que ahí se vacíe la pila,

3.

para evitar reconocimiento de palabras que incidentalmente vacíen la pila de $\mbox{\it AutP\/}'$, colóquese ahí un nuevo delimitador ``derecho'' X' que no pertenezca al alfabeto $\mbox{\it AlfP\/}$ y bórrese sólo en el caso del paso 2.

Lema 2.2   Para cada autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ existe otro autómata de pila $\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$ tal que el lenguaje reconocido por pila vacía en el primer autómata es reconocido por estados finales en el segundo, es decir

$$\mbox{\it LPV\/}(\mbox{\it AutP\/})=\mbox{\it LF\/}(\mbox{\it AutP\/})'$$

En efecto, $\mbox{\it AutP\/}'$ se construye a partir de $\mbox{\it AutP\/}$ como sigue:

1.

colóquese en $\mbox{\it AutP\/}'$ un nuevo símbolo inicial X',

2.

en general, actúese en $\mbox{\it AutP\/}'$ como se hace en $\mbox{\it AutP\/}$,

3.

cuando se vacíe la pila de $\mbox{\it AutP\/}$, es decir, cuando la marca X' acceda al tope de la pila, transítese en $\mbox{\it AutP\/}'$ a un nuevo estado final.

De ahora en adelante supondremos, sin pérdida de generalidad, que el reconocimiento de un lenguaje con un autómata de pila se hace por pila vacía, y consecuentemente no consideraremos más estados finales.
Siguiente: Autómatas de pila y Un nivel arriba: Autómatas de pila Anterior: Principios básicos