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 / Vázquez-De-Parga Andrade, M. (2008). Autómatas finitos: irreducibilidad e Inferencia [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/2321 / Palancia
| Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/2321 |
| Date | 20 June 2008 |
| Creators | Vázquez-De-Parga Andrade, Manuel |
| Contributors | García Gómez, Pedro, Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació |
| Publisher | Universitat Politècnica de València |
| Source Sets | Universitat Politècnica de València |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/acceptedVersion |
| Source | Riunet |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds