Gramaticas

Instituto Tecnológico Superior de Lerdo

Nombre del curso:
Teoría de la computación

Nombre del docente:
Ing. Manuel Juan Guereca Tijerina

Nombre del alumno:
Mayorga Moreno Luis Daniel 08231204

Módulo: Cuarto Semestre Grupo: 4° A

Actividad:

Resumen
Páginas 111 – 120

Fecha: Miercoles, 24 de Marzo del 2010

Gramáticas y lenguajes libres de contexto

LosLenguajes Libres de Contexto (abreviado LLC) forman una clase de lenguajes más
amplia que los Lenguajes Regulares, de acuerdo con la Jerarquía de Chomsky.

Estos lenguajes son importantes tanto desde el punto de vista teórico, por relacionar las llamadas Gramáticas Libres de Contexto con los Autómatas de Pila, como desde el punto de vista práctico, ya que casi todos los lenguajes de programaciónestán basados en los LLC.

Una regla es una expresión de la forma a B, en donde tanto a como B son cadenas de símbolos en donde pueden aparecer tanto elementos del alfabeto ∑ (llamados constantes)
como unos nuevos símbolos, llamados variables.

Consideremos, por ejemplo, la siguiente gramática para producir un pequeño subconjunto del idioma español:
1. <frase> <sujeto><predicado>
2. <sujeto> <articulo> <sustantivo>
3. <articulo> el | la
4. <sustantivo> perro | luna
5. <predicado> <verbo>
6. <verbo> brilla | corre

Por ejemplo, podemos usar la gramática que acabamos de presentar, para generar la frase “el perro corre”. En efecto, partiendo del símbolo inicial <frase>, aplicando laprimera regla podemos obtener <sujeto> <predicado>. Luego, reemplazando <sujeto> por medio de la segunda regla, obtenemos <articulo> <sustantivo> <predicado>; aplicando la tercera regla, llegamos a el <sustantivo> <predicado>. Por la cuarta regla se llega a el perro <predicado>; por la quinta a el perro <verbo>, y finalmente, por la sexta,llegamos a el perro corre.

Gramáticas y la jerarquía de Chomsky

1. Gramáticas regulares, o de tipo 3: las reglas son de la forma A aB o bien A a, donde A y B son variables y a es constante. 6 Estas gramáticas son capaces de describir los lenguajes regulares.

2. Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X a, donde X es una variable y _ es una cadena quepuede contener variables y constantes.

Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”)
.
3. Gramáticas sensitivas al contexto o de tipo 1: las reglas son de la forma aAB L, donde A es una variable y a,B y L son cadenas cualesquiera que pueden contener variables y constantes.

4. Gramáticas no restringidas, o de tipo 0, con reglas de la forma _a B, donde a nopuede ser vacío, que generan los lenguajes llamados “recursivamente enumerables”.

Lenguajes y gramáticas libres de contexto (LLC y GLC)

Por ejemplo, el lenguaje {an bn} –que no es regular tiene la gramática libre de contexto con las siguientes reglas:

1. S aSb
2. S ab

En el caso de las gramáticas regulares, aplicar una regla X a de una gramática consiste en reemplazar X por _ enuna palabra.
Por ejemplo, la regla S aSb se puede aplicar a una palabra aaSbb para obtener la palabra aaaSbbb, en donde es fácil ver que reemplazamos S por aSb.

Al proceso de aplicar una regla se le conoce como “paso de derivación”, y se denota usando una flecha gruesa “)”, como en aaSbb ) aaaSbbb (aplicando una regla S aSb).

Una secuencia de pasos de derivaci´on a partir de una variableespecial de la gramática llamada “s´ımbolo inicial” se llama simplemente derivaci´on. Por ejemplo, una derivación de la palabra “aaabbb” utilizando la gram´atica de {an bn} sería (suponiendo que S es el símbolo inicial):

S aSb aaSbb aaabbb

Como un ejemplo adicional, la gramática con las reglas siguientes permite generar expresiones aritméticas con sumas y multiplicaciones de enteros:
1....