Siguiente: Autómatas de pila Un nivel arriba: Autómatas Anterior: Autómatas

Autómatas regulares

Estos son los autómatas finitos más sencillos. Se construyen a partir de un conjunto de estados Q y de un conjunto de símbolos de entrada T. Su funcionamiento queda determinado por una función de transición $t: Q \times T \rightarrow Q$. Si t(q,s)=p esto se interpreta como que el autómata transita del estado q al estado p cuando arriba el símbolo s. En todo autómata finito se cuenta con un estado inicial, $q_0 \in Q$ y un conjunto de estados finales $F\subset Q$. Con todo esto definido, la estructura $\mbox{\rm AutoReg}= (Q, T, t, q_0, F)$ es un autómata regular. De manera natural, t se extiende a una función de transición $T^*\rightarrow Q$: Toda palabra se aplica al autómata y éste, partiendo del estado inicial, transita con cada símbolo de la palabra dada según lo especifique t, correspondiendo a ese símbolo y al estado actual en el autómata. Una palabra es reconocida por el automata si lo hace arribar a un estado final. El lenguaje del autómata consta de todas las palabras reconocidas.


Ejemplo: Sea $\mbox{\rm AutoReg}= (Q, T, t, q_0, F)$ el autómata cuyo conjunto de estados es $Q = \{a, b, c\}$, el de símbolos de entrada es $T = \{0,1\}$, su estado inicial es q₀ = a y el conjunto de estados finales es $F = \{a\}$. Su transición queda determinada por la tabla

$$\left.\begin{array}{c\vert cc} t & 0 & 1 \\ \hline a & b & a \\ b & c & a \\ c & c & c \end{array}\right\}$$

Observamos que, partiendo del estado a, mientras lleguen 1's se está en el estado inicial, con un 0 se pasa a b, con un segundo 0 se pasa a c y de ahí no se sale más. En b, al llegar un 1 se regresa al estado inicial. Así pues, para arribar al estado a desde a mismo la cadena de entrada ha de ser una sarta de varias de 1's separadas éstas por únicos 0's. En otras palabras, el autómata reconoce al lenguaje (1⁺0)^*1⁺.
Siguiente: Autómatas de pila Un nivel arriba: Autómatas Anterior: Autómatas