Autómatas finitos: irreducibilidad e Inferencia

Abstract

En este trabajo abordamos dos problemas: El de la reducción de autómatas finitos y el de la inferencia de los lenguajes regulares y estudiamos las relaciones entre ellos.

Tras la introducción, en el segundo capítulo se repasan los conceptos y proposiciones básicos de teoría de lenguajes y se establece la notación utilizada a lo largo del trabajo. Lo mismo, pero en lo que concierne a la inferencia gramatical, se realiza en el tercer capítulo, donde se describe además el actual estado del arte. En el cuarto capítulo se discuten los problemas de minimalización y reducción de autómatas finitos y se demuestra el primero de los resultados centrales de esta tesis, la existencia de una cota en el tamaño de los autómatas finitos irreducibles que aceptan un determinado lenguaje regular. Se introducen además los conceptos de irreducibilidad y concisión relativas. En el capítulo quinto se discuten y amplían los conceptos de red de autómatas cocientes y completitud estructural y se introduce el concepto de universalidad estructural. Como resultado de este estudio se obtiene el segundo de los resultados centrales de este trabajo, el cual establece que cualquier algoritmo de fusión de estados que obtenga como resultado un autómata finito irreducible compatible con los datos de entrada infiere en el límite la clase de los lenguajes regulares siempre y cuando se aplique en cierta manera, por lo demás poco restrictiva. En el capítulo sexto se introduce el concepto de subautómata asociado a una palabra en un lenguaje y a partir de él se describe una nueva familia de algoritmos de inferencia de la clase de los lenguajes regulares representados mediante autómatas finitos, algoritmos que tienen la particularidad de que su complejidad temporal es función básicamente de la longitud de las palabras de la muestra de entrada, mientras que son prácticamente lineales respecto al número de las mismas. En el capítulo séptimo se describen algunos algorítmos de las familias menci