Garanmatica

3.1. Concepto de gramática formal
Producciones. Gramática Formal. Lenguaje
asociado a una gramática. Recursividad.
Gramáticas equivalentes.
3.2. Tipos de gramáticas
Jerarquía de Chomsky.Gramáticas de tipos 0, 1,
2, y 3.
3.3. Árboles de derivación
Representación arborescente de derivaciones.
Ambigüedad.
1
3.1 Concepto de gramática formal
· Hemos visto que lenguajes son subconjuntos delas
palabras sobre un alfabeto (LÍW(å)).
· ¿Cómo se puede definir las palabras que pertenecen a un
determinado lenguaje?
 Enumerando el conjunto de palabras
Þ ¿algunos lenguajes son infinitos? Descripción informal de las palabras:
Þ a veces complicado y demasiado impreciso
 Descripción formal, basada en los operadores de
palabras:
Þ no suelen ser suficientes para especificar todos loslenguajes
Necesitamos un formalismo para definir los lenguajes (las
palabras que pertenecen a un lenguaje).
Þ una posibilidad - Gramáticas formales:
 Una gramática describe de forma inequívocala
estructura de las palabras de un lenguaje
 Proporcionan un mecanismo para generar todas las
palabras que pertenecen a un determinado lenguaje
(también se llaman gramáticas3.1. Concepto degramática formal
Producciones. Gramática Formal. Lenguaje
asociado a una gramática. Recursividad.
Gramáticas equivalentes.
3.2. Tipos de gramáticas
Jerarquía de Chomsky. Gramáticas de tipos 0, 1,
2, y3.
3.3. Árboles de derivación
Representación arborescente de derivaciones.
Ambigüedad.
1
3.1 Concepto de gramática formal
· Hemos visto que lenguajes son subconjuntos de las
palabras sobre unalfabeto (LÍW(å)).
· ¿Cómo se puede definir las palabras que pertenecen a un
determinado lenguaje?
 Enumerando el conjunto de palabras
Þ ¿algunos lenguajes son infinitos?
 Descripción informalde las palabras:
Þ a veces complicado y demasiado impreciso
 Descripción formal, basada en los operadores de
palabras:
Þ no suelen ser suficientes para especificar todos los
lenguajes...