Lenguiajes de la computacion

INDICE

Portada …………………………………………………………………………………….

Contenido …………………………………………………………………………………….

Conclusiones …………………………………………………………………………………….

Bibliográficas …………………………………………………………………………………….

LENGUAJES LIBRES DE CONTEXTO
 
  Para cualquier lenguaje libre de contexto L existe un autómata de pila que reconoce al lenguaje, i.e.: libre de contexto y sea G una gramática libre decontexto 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 `` '' sedemuestra 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 yapliquemos lo anterior para encontrar un autómata de pila que reconozca a G1. Ampliemos, finalmente, a añadiendo la transición .

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 [pic]que reconoce al lenguaje, i.e.: [pic].
Sea L un lenguaje libre de contexto y sea G unagramá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 [pic]donde
[pic]

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 laequivalencia
[pic]

(La implicación `` [pic]'' se demuestra mediante inducción en el número de producciones utilizadas en una derivación siniestra de [pic]. El recíproco `` [pic]'' se demuestra mediante inducción en el número de transiciones aplicadas para derivar la descripción final [pic]a partir de la inicial [pic]en [pic].) Ahora bien, si L contuviera a la palabra vacía [pic], entonces, anulemos atodas las producciones- [pic], o anulables, en una gramática que genere a [pic]y apliquemos lo anterior para encontrar un autómata de pila [pic]que reconozca a G1. Ampliemos, finalmente, a [pic]añadiendo la transición [pic].

Definición formal

Así como cualquier gramática formal, una gramática libre de contexto puede ser definida mediante la 4-tupla:
G = (Vt,Vn,P,S) donde
• Vt es unconjunto finito de terminales
• Vn es un conjunto finito de no terminales
• P es un conjunto finito de producciones
• [pic]el denominado Símbolo Inicial
• los elementos de P son de la forma
[pic]

Ejemplos

Ejemplo 1

Una simple gramática libre de contexto es
S → aSb | ε

donde | es un o lógico y es usado para separar múltiples opciones para el mismo noterminal, ε indica una cadena vacía. Esta gramática genera el lenguaje no regular [pic].

Ejemplo 2

Aquí hay una gramática libre de contexto para expresiones enteras algebraicas sintácticamente correctas sobre las variables x, y y z:
S → x | y | z | S + S | S - S | S *S | S/S | (S)

Generaría, por ejemplo, la cadena (x + y) *x - z *y / (x + x)

Ejemplo 3

Una gramática libre decontexto para un lenguaje consistente en todas las cadenas que se pueden formar con las letras a y b, habiendo un número diferente de una que de otra, sería:
S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

T genera todas las cadenas con la misma cantidad de letras a que b, U genera todas las cadenas con más letras a, y V todas las cadenas con más letras...