next up previous contents
Siguiente: Series de potencias e Un nivel arriba: Lenguajes libres de contexto Anterior: Forma normal de Greibach

Lenguajes libres de contexto y autómatas de pila

Veamos que todo lenguaje libre de contexto es reconocido por una autómata de pila.

Proposición 4.1   Para cualquier lenguaje libre de contexto L existe un autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,\emptyset)$ que reconoce al lenguaje, i.e.: $L=\mbox{\it LPV\/}(\mbox{\it AutP\/})$.

Sea L un lenguaje libre de contexto y sea G una gramática libre de contexto que lo genere. Supongamos por un momento que la palabra vacía no pertenezca al lenguaje L. Podemos pues suponer que la gramática G=(V,T,P,S) está en forma normal de Greibach. Sea $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ donde

\begin{eqnarray*}Q=\{q_0\} &:& \mbox{\rm consta de un \'unico estado,} \\
\mbo...
...olo \lq\lq inicial'' para la pila es el inicial de la gram\'atica.}
\end{eqnarray*}


La función del autómata definido es la de simular derivaciones siniestras, en la gramática G, de palabras en el lenguaje L. De hecho, se puede demostrar que se cumple la equivalencia

\begin{displaymath}G\vdash \left(S\stackrel{*}{\Rightarrow}\sigma\right)\ \Leftr...
...el{*}{\Rightarrow}q_0\mbox{\it nil\/};\mbox{\it nil\/}\right)
\end{displaymath}

(La implicación `` $\Rightarrow)$'' se demuestra mediante inducción en el número de producciones utilizadas en una derivación siniestra de $\sigma$. El recíproco `` $\Leftarrow )$'' se demuestra mediante inducción en el número de transiciones aplicadas para derivar la descripción final $q_0\mbox{\it nil\/};\mbox{\it nil\/}$ a partir de la inicial $q_0\sigma;X_0$ en $\mbox{\it AutP\/}$.) Ahora bien, si L contuviera a la palabra vacía $\mbox{\it nil\/}$, entonces, anulemos a todas las producciones- $\mbox{\it nil\/}$, o anulables, en una gramática que genere a $G_1=G-\{nil\}$ y apliquemos lo anterior para encontrar un autómata de pila $\mbox{\it AutP\/}_1$ que reconozca a G1. Ampliemos, finalmente, a $\mbox{\it AutP\/}_1$ añadiendo la transición $(q_0,\mbox{\it nil\/})\in\mbox{\it tran\/}(q_0,\mbox{\it nil\/},S)$.
next up previous contents
Siguiente: Series de potencias e Un nivel arriba: Lenguajes libres de contexto Anterior: Forma normal de Greibach
Guillermo Morales-Luna
2000-06-27