Automatas

UNIVERSIDAD COOPERATIVA DE COLOMBIA
Automatas y Gramaticas

Presentado por:
Carlos Eduardo Garay Forero
Cod: 108081173
Edicson Villanueva G.
Cod: 8021013

Presentado a:
Ing. Julio Ferrer

UNIVERSIDAD COOPERATIVA DE COLOMBIA
Facultad Ingeniería de Sistemas
Inteligencia Artificial
26/09/11
GRAMATICAS

Una gramática libre del contexto es un cuarteto

G= (V,T,P,S)

Donde:V.- Conjunto de Variables
T.- Conjunto de Terminales
P.- Conjunto de Reglas de Producción
S.- Símbolo inicial de la gramática

Las reglas de producción son de la forma

Donde y

Como el número de reglas de producción es finito, las gramáticas libres del contexto son la mejor manera de describir lenguajes libres del contexto, los cuales son normalmente conjunto infinitos, parasaber si una cadena forma parte de un lenguaje podemos verificar si se puede derivar a partir del símbolo inicial de la gramática, es decir

Observe que en las reglas de producción usamos la flecha sencilla o delgada, mientras que en las derivaciones utilizamos la flecha doble o gruesa.

Ejemplo, la siguiente gramática describe el Lenguaje que consiste de todas las cadenas hechas con ceros yunos que son palíndromos:

G=({A},{0,1},P,A)

Donde P consiste de las siguientes CINCO reglas de producción

Observe que la última línea tiene realmente 3 reglas de producción ya que la barra vertical debe leerse como “o´”, es decir, la última linea dice que la Variable A produce 1 o bien 0 o finalmente la cadena vacía.

A veces obviamos la especificación comoG=({A},{0,1},P,A), y escribimos directamente las reglas de producción, en cuyo caso la variable que está a la izquierda de la primer regla de producción se toma como el símbolo inicial de la gramática, acostumbramos también utilizar mayúsculas para denotar variables, pero esto no se puede hacer cuando las cadenas que constituyen el lenguaje pueden incluirlas.

Derivemos la cadena 001100

Este lenguajepor cierto no puede describirse mediante ninguna expresión regular, si bien las gramáticas regulares pueden denotar a los lenguajes regulares, las expresiones regulares no pueden denotar a todos los lenguajes libres del contexto, ya que estos son un superconjunto de los lenguajes regulares.

Veamos otro ejemplo de lenguaje que no puede ser descrito por ninguna expresión regular, se trata deuna gramática que denota al conjunto de cadenas que son expresiones algebraicas que utilizan solo a las variables algebraicas x y y.

Aquí G=({E},{+,-,*,/,(,)x,y},P,E), se trata pues de otro ejemplo donde solo se usa una varible, este tipo de gramáticas casi simpre presentan un problema.

Hagamos una derivación de la cadena x+y*x

La derivación se pudo haber realizado utilizando las reglasde producción en un orden diferente, por ejemplo, la siguiente también es una derivación válida:

Cuando es posible realizar dos derivaciones distintas de una misma cadena, decimos que la grampatica es AMBIGUA, la ambigüedad presenta muchos problemas en la préctica, puesto que en una aplicación real, por ejemplo una calculadora pudiera decirnos que 3+2*3 es igual a quince en lugar de nueve yaque las gramáticas como estas no proporcionan información acerca de la jerarquía de operadores
FORMA NORMAL DE CHOMSKY (FNC)

Una gramática sin reglas de producción unitarias, sin símbolos inútiles ni anulables puede expresarse en la FNC, en la cual todas las reglas de producción tienen del lado derecho un terminal o bien 2 variables, es decir, las reglas de producción son de la formadonde
Ó bien, de la forma
donde

Ejemplo, convirtamos la gramática siguiente a la FNC

Solución:
La primera regla de producción la podemos cambiar por las tres siguientes

La segunda regla de producción la podemos cambiar por las tres siguientes

Las últimas dos reglas sí cumplen con la FNC, entonces la gramática normalizada queda:

GRAMÁTICAS TIPO 0

También llamadas...