Siguiente: Homomorfismos Un nivel arriba: Autómatas finitos Anterior: Autómatas finitos

Conceptos básicos

En la sección anterior se vió que basta considerar a las máquinas de Moore en el estudio de las propiedades relativas a las máquinas finitas. Más aún, en las máquinas de Moore se puede omitir a la función de respuesta y considerar que en cada estado, el símbolo que se emite al llegar a él es precisamente la etiqueta con que se ``distingue'' a ese estado. Por tanto, si se está interesado en reconocer a todas las palabras que al final emiten un símbolo determinado, bastará con distinguir como finales a los estados que emiten ese símbolo. Las palabras reconocidas son todas aquellas que llegan a los estados finales a partir del estado inicial. Un autómata finito (determinista) es pues una estructura de la forma

$$\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$$

donde

$$\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...bset Q &:& \mbox{\rm es el conjunto de estados {\em finales}.} \end{eqnarray*}$$

Un semiautómata finito es una estructura de la forma

$$\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$$

es decir, es un ``autómata finito'' en el que no se ha especificado estados finales. Todo autómata finito puede ser visto como un semiautómata con estados finales distinguidos. El semiautómata determinado por un autómata se dice ser el semiautómata subyacente del autómata. Todas las nociones y aseveraciones hechas sobre semiautómatas serán válidas también en los autómatas de los que son subyacentes. Como en las máquinas finitas, ya sea de Mealy o de Moore, en cada semiautómata extendemos la función de transición $\mbox{\it tran\/}:Q\times \mbox{\it Ent\/}\rightarrow Q$ a una función $\mbox{\it tran\/}^*:Q\times \mbox{\it Ent\/}^*\rightarrow Q$, haciendo, para cada estado $q\in Q$:

$$\begin{eqnarray*}\mbox{\it tran\/}^*(q,\mbox{\it nil\/}) &=& q,\\ \forall \sig... ...sigma s) &=& \mbox{\it tran\/}(\mbox{\it tran\/}^*(q,\sigma),s) \end{eqnarray*}$$

Sea $T:\mbox{\it Ent\/}^*\rightarrow Q$ la función $\sigma\mapsto T(\sigma)=\mbox{\it tran\/}^*(q_0,\sigma)$. Un estado $q\in Q$ se dice ser accesible si está en la imagen de T, es decir, si $\exists \sigma\in\mbox{\it Ent\/}^* : T(\sigma)=q$. La parte accesible de $\mbox{\it AF\/}$ es la imagen de T, es decir, consta de todos los estados accesibles a partir del estado inicial.

Lema 2.1   Sea $\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ un semiautómata finito. Cualquier estado accesible se alcanza mediante una palabra de longitud a lo sumo el número total de estados, $n=\mbox{\rm card}(Q)$. En otras palabras, la parte accesible del semiautómata coincide con el conjunto $\mbox{\it Acc\/}(\mbox{\it SAF\/})=\{T(\sigma)\vert\mbox{\rm long}(\sigma)\leq\mbox{\rm card}(Q)\}.$

En efecto, para cada $m\in I\!\!N$ sea $\mbox{\it Ent\/}^{(m)}={\displaystyle \bigcup_{\mu\leq m}\mbox{\it Ent\/}^{\mu}}$ el conjunto de palabras de longitud a lo sumo m. La colección de conjuntos es un recubrimiento (creciente) del diccionario $\mbox{\it Ent\/}^*$ mediante conjuntos anidados:

$$\begin{eqnarray*}&&\mbox{\it Ent\/}^*=\bigcup_{m\geq 0}\mbox{\it Ent\/}^{(m)} \h... ...1)}]\land [\mbox{\it Ent\/}^{(m)}\not=\mbox{\it Ent\/}^{(m+1)}] \end{eqnarray*}$$

Consecuentemente, $\{T(\mbox{\it Ent\/}^{(m)})\}_{m\geq 0}$ es también un recubrimiento de Q mediante conjuntos anidados. Por ser Q finito, necesariamente para algún índice m₀ se ha de tener que $T(\mbox{\it Ent\/}^{(m_0)})=T(\mbox{\it Ent\/}^{(m_0+1)})$, y, de hecho, para todo $m\geq m_0$, $T(\mbox{\it Ent\/}^{(m)})=T(\mbox{\it Ent\/}^{(m_0)})$. Así pues, se tiene una cadena finita de inclusiones,

$$\{q_0\}=T(\mbox{\it Ent\/}^{(0)})\subset \cdots \subset T(\mbox{\it Ent\/}^{(m_0)}) \subset Q.$$

Como cualesquiera dos conjuntos consecutivos $T(\mbox{\it Ent\/}^{(k)})$, $T(\mbox{\it Ent\/}^{(k+1)})$ pueden diferir en al menos un elemento en Q se tiene que $m_0\leq n$. Además, $T(\mbox{\it Ent\/}^{*})=T(\mbox{\it Ent\/}^{(m_0)})$. De aquí se sigue la tesis del lema, quod erat demonstratum (q.e.d.).


La parte accesible, $\mbox{\it SAF\/}^{\mbox{\scriptsize\it acc}}$, de un semiautómata $\mbox{\it SAF\/}$ consta de todos sus estados accesibles. Naturalmente, se tiene un algoritmo elemental para construir la parte accesible de cualquier semiautómata finito:

1.

Consideremos dos listas: una de estados ya revisados y otra de estados por revisar. Inicialmente la primera está vacía y la segunda consta sólo del estado inicial.

2.

Para cada estado por revisar,

(a)

se toma a ese estado como actual q,

(b)

para cada símbolo de entrada $e\in\mbox{\it Ent\/}$ sea $p=\mbox{\it tran\/}(q,e)$. Si p aparece en alguna de las dos listas se pasa al siguiente símbolo, en otro caso se lo coloca al final de los estados a revisar,

(c)

se coloca el estado actual en la lista de los ya revisados.

En la figura 3.5 se presenta un seudocódigo de este algoritmo.

  

Figure 3.5: Cálculo de la parte accesible.

El lema anterior implica que el número de iteraciones en el ciclo principal del algoritmo anterior no excede al número de estados en el autómata.


Ejemplo. Si $\mbox{\it Ent\/}=\{1\}$ consta de un único símbolo entonces el algoritmo 3.5 muestra que la parte accesible tiene forma de la letra griega ``rho'', $\rho$, es decir, existen $n,m\geq 0$ tales que

$$q_0\stackrel{1}{\rightarrow}q_1\stackrel{1}{\rightarrow}\cdot... ...n+m} \stackrel{1}{\rightarrow}q_{n}}_{\mbox{\scriptsize ciclo}}$$

Sea $\mbox{\it AF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ un autómata finito. Decimos que una palabra $\sigma \in \mbox{\it Ent\/}^*$ es reconocida por A si $T(\sigma)\in F$, es decir, $\sigma$ es reconocida si al aplicarla a $\mbox{\it AF\/}$ desde el estado inicial se arriba a uno de los estados finales. El lenguaje reconocido por $\mbox{\it AF\/}$ consta de todas las palabras reconocidas por $\mbox{\it AF\/}$:

$$L(\mbox{\it AF\/})=\{\sigma\in\mbox{\it Ent\/}^*\vert T(\sigma)\in F\}=T^{-1}(F).$$

Diremos que un autómata $\mbox{\it AF\/}_1$ subsume a otro autómata $\mbox{\it AF\/}_2$ si $L(\mbox{\it AF\/}_2)\subset L(\mbox{\it AF\/}_1)$. La relación de ``subsunción'' es reflexiva y transitiva. Diremos que dos autómatas son equivalentes si uno subsume al otro, es decir, si coinciden los lenguajes reconocidos por ellos. Esta es una relación de equivalencia entre autómatas. Diremos que un lenguaje $L\subset\mbox{\it Ent\/}^*$ es regular-AF si existe un autómata finito $\mbox{\it AF\/}$ tal que $L=L(\mbox{\it AF\/})$.


Ejemplos. Sea $\mbox{\it Ent\/}=\{0,1\}$. 1. Construyamos un autómata que reconozca cadenas binarias con números pares de 0's y de 1's. Consideremos los estados siguientes:

$$\begin{eqnarray*}q_0 &:& \mbox{\rm n\'umero par de 0's y n\'umero par de 1's,} \... ... &:& \mbox{\rm n\'umero impar de 0's y n\'umero impar de 1's.} \end{eqnarray*}$$

La tabla de transición queda definida de manera natural:

$$\begin{array}{\vert\vert r\vert cc\vert\vert}\hline\hline \... ... & q_0 & q_3 \\ q_3 & q_1 & q_2 \\ \hline\hline \end{array}$$

El estado inicial es q₀ y el conjunto de estados finales es $F=\{q_0\}$. Es fácil ver que el lenguaje reconocido por este autómata es

$$L=\{\sigma\in\mbox{\it Ent\/}^*\vert(\mbox{\rm No. de 0's en ... ...m mod }2=0=(\mbox{\rm No. de 1's en }\sigma)\mbox{\rm mod }2\}.$$

El lenguaje L es pues regular-AF. En este ejemplo, es también muy fácil ver que para cada $\sigma \in \mbox{\it Ent\/}^*$, $T(\sigma)$ queda determinada por las paridades de 0's y de 1's en $\sigma$.


2. Consideremos el autómata con tabla de transición

$$\begin{array}{\vert\vert r\vert cc\vert\vert}\hline\hline \... ... & q_3 & q_2 \\ q_3 & q_3 & q_3 \\ \hline\hline \end{array}$$

y estado inicial q₀. Observemos que

• si se arriba al estado q₃ ya no se sale de ahí,
• se arriba a q₃ si inicialmente aparece un 1 y no hay 0's que lo precedan, o bien, habiendo llegado un bloque de 0's y luego uno de 1's, reaparece un 0.

Así pues, si el conjunto de estados finales es $F=\{q_2\}$ entonces el lenguaje reconocido por este autómata es $L=\{0^n1^m\vert n,m>0\}.$
Siguiente: Homomorfismos Un nivel arriba: Autómatas finitos Anterior: Autómatas finitos