AdeS

Departamento de Tecnologías de la Información

Tema 3: Fundamentos de la

Teoría de Gramáticas
Formales

Ciencias de la Computación e Inteligencia Artificial

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales

Índice

3.1. Concepto básico de Gramática. Ejemplos
3.2. Concepto de gramática formal
3.3. Tipos de Gramáticas. Jerarquía de Chomsky
3.4. Árboles de derivación
3.5.Ambigüedad
3.6. Recursividad
3.7. Factorización a izquierdas

2

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales

Índice

3.1. Concepto básico de Gramática. Ejemplos
3.2. Concepto de gramática formal
3.3. Tipos de Gramáticas. Jerarquía de Chomsky
3.4. Árboles de derivación
3.5. Ambigüedad
3.6. Recursividad
3.7. Factorización aizquierdas

3

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales

3.1 Concepto básico de
Gramática. Ejemplos

• Una gramática define la estructura de las frases y
de las palabras de un lenguaje.

• Las gramáticas son un método para la generación
de palabras de un lenguaje a partir de un alfabeto.
– para generar estas palabras seutilizan las derivaciones.
– se denominan formales porque se centran en los estudios
de los lenguajes formales que son aquellos que están
definidos a partir de reglas preestablecidas. Para los
lenguajes naturales existen otro tipo de gramáticas.

4

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales
•

3.1 Concepto básico de
Gramática.Ejemplos

La gramática de la lengua castellana se expresa mediante reglas sencillas que
definen las partes de la oración, y que permiten comprobar fácilmente si una
frase determinada es o no correcta. Analizar la frase “La niña pedía comida a
María en el parque”.
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
::= < circunstancial>
::=
::=
::= 
::=
::=::= “a”
::=
5

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales
•

3.1 Concepto básico de
Gramática. Ejemplos

Obsérvese la existencia de recursividad en las reglas de producción. Algunas
la introducen directamente, como en el caso ::=
, mientras que en otras de forma indirecta
( ).

•

Para completar las reglas sintácticasanteriores se necesita información

morfológica sobre las palabras. Esta información también puede escribirse en
forma de reglas de producción:
::= “niña”
::= “María”
::= “comida”
::= “parque”
::= “la”
::= “pedía”
::= “en”
6

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales

3.1 Concepto básico de
Gramática. Ejemplos

•Teniendo en cuenta todas estas reglas, y aplicando el concepto de
derivación, se puede obtener la frase considerada partiendo de una
palabra de una sola letra :






 la
 la niña
 la niña
 la niña pedía
 la niña pedía
 la niña pedía comida

7

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales










3.1 Concepto básico de
Gramática. Ejemplos

la niña pedía comida a
la niña pedía comida a
la niña pedía comida a
la niña pedía comida a María
la niña pedía comida a María
la niña pedía comida a María en
la niña pedía comida a María en
la niña pedía comida a María en
la niña pedía comida a María en el
la niña pedía comida a María en el parque

• Por tanto,al haber una derivación que produce dicha frase
partiendo de , se sigue que se trata de una frase correcta
que pertenece al lenguaje representado por la gramática.

8

Teoría de Autómatas y Lenguajes Formales

Tema 3: Fundamentos de la
Teoría de Gramáticas Formales

3.1 Concepto básico de
Gramática. Ejemplos

• Ejemplo: consideremos la instrucción de cualquier lenguaje x = y+2*z...