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

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

(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 G₁. 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)$.
Siguiente: Series de potencias e Un nivel arriba: Lenguajes libres de contexto Anterior: Forma normal de Greibach