Copyright: Ayuda creada por: Beatriz Corzo Menéndez             1999


Introduccion
Introducción a la Inducción Gramatical

Inducción gramatical

Tipos de algoritmos

Ejemplo


Induccion Gramatical
¿Qué es la Inducción Gramatical?

Ejemplo

El problema de la inducción gramatical consiste en inducir una gramática o lenguaje a partir de una muestra finita de cadenas. El alcance de este resumen queda restringido a los lenguajes regulares. Para ello se utiliza como apoyo los autómatas finitos, y como fundamento el teorema que asegura igual capacidad computacional para gramáticas regulares y autómatas finitos:

"Para todo autómata finito, existe una gramática regular y una expresión regular tales que el lenguaje generado por la gramática y el representado por la expresión regular coincide con el lenguaje reconocido por el autómata finito."

Existen técnicas algorítmicas que permiten construir autómatas finitos partiendo de la información que proporciona una muestra de ejemplos y, en algunos casos, de información añadida: valores de parámetros, ejemplos negativos, etc. Estas técnicas se basan en lo que se conoce como inducción gramatical y su desarrollo es el objetivo de esta documentación.

Se verán diferentes tipos de algoritmos que infieren un lenguaje regular a partir de un subconjunto del mismo.


Tipos de Algoritmos

Los tipos de algoritmos que pueden inferir un cierto lenguaje se dividen en:

•	Algoritmos incrementales, en los cuales se introducen los ejemplos uno a uno; con los primeros ejemplos se obtiene una primera aproximación del autómata, con el siguiente ejemplo añadido se modifica el autómata anterior, sólo si es necesario, para que éste reconozca a la nueva cadena y así sucesivamente con todos los ejemplos que se añadan. Si a partir de un cierto ejemplo los siguientes ya no modifican el autómata se dice que el lenguaje es límite.

•	Algoritmos  no incrementales, en este caso, la inducción se realiza con la muestra completa y un ejemplo nuevo añadido supone volver a construir un nuevo autómata con la muestra incrementada en ese ejemplo.


Ejemplo Induccion
Ejemplo Inducción Gramatical

Partiendo de una muestra positiva  S+ = {aabb, ab, aab, abbb},	el problema que nos ocupa consistiría en inducir la gramática o autómata que genere un lenguaje regular englobando la muestra y para el que la muestra resulte representativa.

En este caso la gramática podría ser a+ b+, o bien, aa* bb*

La solución no tiene por que ser única.


Muestra Positiva
Se denotará por  S+  al conjunto de ejemplos positivos; es decir,

cadenas que pertenecen al lenguaje, llamado también muestra positiva.


Muestra Negativa
Se denotará por  S-  al conjunto de ejemplos negativos; es decir,

cadenas que no pertenecen al lenguaje, llamado también muestra negativa.


Significado signos
El símbolo  ∗  indica que ese carácter puede aparecer de 0 a n veces.

  	El símbolo  +  indica que ese carácter debe aparecer al menos una vez.


Lenguaje Regular
Se dice que un lenguaje, que denotaremos por L, es regular si existe un autómata finito, (o equivalentemente una gramática regular, o una expresión regular) que lo defina.