Automatas

 2.1 DEFINICIONES BÁSICAS

Un autómata finito (FA) 1 consiste en un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto Σ. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado). Un estado, por lo general denotado como q0, es el estado inicial, en el que el autómata comienza. Algunos estados están designados como final o de aceptación.

A un FA se le asocia un grafo dirigido, conocido como diagrama de transiciones, de la manera siguiente. Los vértices del grafo corresponden a los estados del FA. Si existe una transición del estado q al p sobre la entrada a, entonces existe un arco con etiqueta a que va del estado q al p, en el diagrama de transiciones. El FA acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce del estado inicial a un estado de aceptación. Denotamos formalmente a un autómata finto por el conjuntó de cinco cantidades (Q, Σ, ʃ, q0, F), en el que Q es un conjunto finito de estados, Σ un alfabeto de entrada finito, q0, elemento de Q, el estado inicial, F≤Q conjunto de estados finales y ʃ la función de transición que transforma Q xΣ en Q. Esto es, ʃ (q, a) es un estado para cada estado q y símbolo de entrada a.

Visualizamos a un FA como un control finito, que se encuentra etiquetado algún estado de Q, y que lee una secuencia de símbolos de Σ escritos en una cinta, según se muestra en la Fig. 2.3. En un movimiento, el FA que se encuentra en el estado q y está leyendo el símbolo a, entra al estado ʃ(q, a) y mueve su cabeza un símbolo hacia la derecha. Si ʃ(q, a) es un estado de aceptación, entonces se considera que el FA ha aceptado la cadena escrita en su cinta de entrada hasta la posición a la que se ha movido la cabeza, sin incluir dicha posición. Si la cabeza se ha movido fuera del extremo derecho de la cinta, entonces el FA acepta a la cinta completa. Nótese que conforme un FA barre una cadena, puede aceptar muchos prefijos diferentes.

 Para describir formalmente el comportamiento de un FA sobre una cadena necesitamos extender la función de transición ʃ para que se pueda aplicar a un estado y una cadena, más que a un estado y un símbolo. Definimos una función de Q x Σ* a Q. La intención es que (q, w) represente al estado en el que estará el FA después de leer la cadena w del estado q. Dicho de otra forma, (q,w) es el único estado p tal que, existe una trayectoria en el diagrama de transiciones de q a p , con la etiqueta w. De manera formal, definimos

...