## 2.4.2 ALGORITMO CON AUTÓMATA FINITO

Dado un patrón P, es posible construir un autómata finito que sirva para buscar con gran rapidez una copia de P en el texto. Podemos interpretar fácilmente un autómata finito como tipo especial de máquina o de diagrama de flujo, pero no es necesario tener conocimientos de teoría de autómatas para entender este método.

Definición

Sea Σ el alfabeto, o conjunto de caracteres, del cual pueden escogerse los caracteres de P y de T, y sea α=|Σ|. El diagrama de flujo, o autómata finito, tiene dos tipos de nodos:

1. Algunos nodos de lectura que significan: “Leer el siguiente carácter del texto. Si no hay más caracteres en la cadena de texto, parar; no hay coincidencia”. Un nodo de lectura se designa como nodo de inicio.
2. Un nodo de paro que significa: “Parar; se halló una coincidencia”. Se le marca con un asterisco. (*).

El diagrama de flujo tiene α flechas que salen de cada nodo de lectura. Cada flecha está rotulada con un carácter de Σ. La flecha que coincide con el carácter de texto que se acaba de leer es la flecha a seguir; es decir, indica el nodo que se visitará a continuación. Los nodos de lectura sirven como una especie de memoria. Por ejemplo, si la ejecución llega al tercer nodo de lectura, es porque los últimos dos caracteres leídos del texto fueron A. Los de antes no tienen importancia.

Para que haya una coincidencia, deben seguir inmediatamente una B y una C. Si el siguiente carácter es una B, podremos parar al nodo 4, que ya apareció AAB. Por otra parte si el siguiente carácter leído en el nodo 3 hubiera sido un Cm tendríamos que haber regresado al nodo 1 y esperar a que aparezca otra A para iniciar el patrón.

Una vez construido el diagrama de flujo para el patrón, se puede probar el texto para ver si ocurre en él el patrón examinando cada carácter del texto una sola vez y por ende en tiempo O(n).

La dificultad radica en la construcción del autómata finito; es decir, en decidir a donde apuntan todas las flechas. Existen algoritmos muy conocidos para construir un autómata finito que reconozca un patrón dado, pero en el peor caso esos algoritmos requieren mucho tiempo. La dificultad se debe al hecho de que de cada nodo de lectura sale una flecha y espacio para representar mα flechas. Por tanto, un mejor algoritmo tendría que eliminar algunas de las flechas.

###