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
que reconoce al lenguaje, i.e.:
.
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
donde
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
(La implicación ``
'' se demuestra mediante inducción en el número de producciones utilizadas en una derivación siniestra de .
El recíproco ``
'' se demuestra mediante inducción en el número de transiciones aplicadas para derivar la descripción final
a partir de la inicial
en
.)
Ahora bien, si L contuviera a la palabra vacía
,
entonces, anulemos a todas las producciones-
,
o anulables, en una gramática que genere a
y apliquemos lo anterior para encontrar un autómata de pila
que reconozca a G1. Ampliemos, finalmente, a
añadiendo la transición
.
Siguiente:Series de potencias eUn nivel arriba:Lenguajes libres de contexto Anterior:Forma normal de GreibachGuillermo Morales-Luna
2000-06-27