automatas

APLICACIÓN QUE TIENEN LOS AUTÓMATAS FINITOS EN LAS CIENCIAS COMPUTACIONALES

BUSQUEDA DE TEXTO
= AUTÓMATAS FINITOS NO DETERMINISTAS =
Supongamos que tenemos un conjunto de palabras, quedenominaremos palabras clave, y deseamos hallar las apariciones de cualquiera de estas palabras. En aplicaciones de este tipo, una forma útil de proceder consiste en diseñar un autómata finito nodeterminista que indique, mediante un estado de aceptación, que ha encontrado una de las palabras clave. El texto de un documento se introduce carácter a carácter en este AFN, el cual reconoce a continuaciónlas apariciones de las palabras clave en dicho texto. Existe una forma simple para que un AFN reconozca un conjunto de palabras clave.

= UN AFD PARA RECONOCER UN CONJUNTO DE PALABRAS CLAVE =Podemos aplicar la construcción de subconjuntos a cualquier AFN. Sin embargo, cuando aplicamos dicha construcción a un AFN que fue diseñado a partir de un conjunto de palabras, comprobamos que el número deestados del AFD nunca es mayor que el número de estados del AFN. Puesto que en el caso peor, el número de estados crece exponencialmente, esta observación es una buena noticia y explica por qué seusa frecuentemente el método de diseñar un AFN para las palabras clave y luego construir un AFD a partir de él.

LIBROS CONSULTADOS
Jonh E. Hpocroft, Rajeev Motwani y Jeffrey D. Ullman“Introducción a la teoría de autómatas, Lenguajes y Computación”
“Lenguajes, Gramáticas y Autómatas” un enfoque práctico
Autores: Pedro Isasi, Paloma Martínez y Daniel Borrajo
Editorial: Addison WesleyDentro del tema de descripción de patrones textuales, se podría contemplar la información agregando un poco del tema que yo investigue, el cual fue “Búsqueda de Texto”, donde a través del siguienteejemplo se describe la manera en cómo funciona un Autómata Finito en la Búsqueda de Texto:
Supongamos que tenemos un conjunto de palabras, que denominaremos palabras clave, y deseamos hallar las...