Tema 4. Gramáticas formales: definiciones, operaciones, tipos de lenguajes, ambigüedad, equivalencia

• 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 se utilizan 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.

Operaciones: 

Para poder definir la dinámica asociada a una gramática, necesitamos asociarle un sistema de transición.

Lenguajes:

Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de símbolos primitivos.

Ej: El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9

Dichas cadenas están formadas gracias a un alfabeto y a una gramática que están formalmente especificados:

*El alfabeto es un conjunto finito no vacío de símbolos

*La gramática es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del alfabeto

*A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada (o palabra) del lenguaje.

Un lenguaje regular es un lenguaje formal que tiene estas características:

*Puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen)

*Puede ser generado mediante una gramática regular (obtener todas las cadenas de símbolos que le pertenecen)

*Puede ser reconocido mediante un autómata finito (saber si una cadena de símbolos pertenece a él o no) 

Un lenguaje incontextual es un lenguaje formal que tiene estas características:

*Puede ser generado mediante una gramática incontextual (obtener todas las cadenas de símbolos que le pertenecen)

*Puede ser reconocido mediante un autómata con pila (saber si una cadena de símbolos pertenece a él o no) 

Ambigüedad:

Se dice que una sentencia es ambigua cuando para una misma sentencia podemos tener varios árboles de derivación diferentes. (Como se vio en el ejemplo anterior, una misma sentencia puede obtenerse como resultado de varias derivaciones diferentes, pero a las que les corresponde un único árbol de derivación.) 

Se dice que una gramática es ambigua si tiene al menos una sentencia ambigua. 

Se dice que un lenguaje es ambiguo si existe una gramática ambigua que lo genera. 

Ejemplo : – G = ({i, +, *, (, )}, {E}, E, E ::= E + E | E * E | ( E ) | i }) – Consideremos la sentencia i+i*i. Para esta sentencia podemos tener los siguientes árboles de derivación :

Esto no quiere decir que el lenguaje sea ambiguo, ya que se puede encontrar una gramática equivalente a la anterior, sin ser ambigua. Pero hay lenguajes para los cuales es imposible encontrar gramáticas no ambiguas. Estos lenguajes se denominan “inherentemente ambiguos”.