Autómatas finitos no-deterministas con transiciones $\epsilon$ (AFND-$\epsilon$)

Queremos construir un autómata que acepta el lenguaje

$$L=\{a^ib^jc^k \;\vert\;i,j,k \in\bbbn\}$$

Si fuesemos capaz de saltar mágicamente, es decir, sin consumir una letra de la entrada, de un estado a otro, sería fácil la construcción:

Es decir, hemos introducido aristas marcados con la palabra vacía $\epsilon$.

Un autómata finito no-determinista con transiciones $\epsilon$ (AFND-$\epsilon$) es una quíntupla

$$M=(\Sigma,Q,\delta,q_0,F)$$

donde

• $Q$, $\Sigma$, $q_0$, y $F$ están definidos igual como en el caso de un AFND
• $\delta$ es
  • una relación, es decir $\delta\subset(Q\times(\Sigma\cup\{\epsilon\}))\times Q$
  • o una función, es decir, $\delta\;:\;Q\times(\Sigma\cup\{\epsilon\}) \longrightarrow {\cal P}(Q)$ siendo ${\cal P}(Q)$ el conjunto de las partes de $Q$

Observamos que añadir más aristas con $\epsilon$ obviamente no cambia el comportamiento del autómata:

Podemos tratar las transiciones con $\epsilon$ como una relación $T$ sobre el conjunto de estados, es decir

$$T=T_1=\{(q,p)\;\vert\;\delta(q,\epsilon)=p\}\subset Q\times Q$$

En el ejemplo tenemos

$$T_1=\{(q_0,q_1),(q_1,q_2)\}$$

Esta relación podemos ampliar para que sea reflexiva, es decir, que todas las parejas $(q,q)$ con $q\in Q$ formen parte de la relación, es decir, formamos

$$T_0=\{(q,q)\;\vert\;q\in Q\}$$

y con eso

$$T=T_0\cup T_1$$

entonces $T$ por construcción es una relación reflexiva. En el ejemplo tenemos

$$T_0=\{(q_0,q_0),(q_1,q_1),(q_2,q_2)\}$$

y con eso

$$T=\{(q_0,q_0),(q_0,q_1),(q_1,q_1),(q_1,q_2),(q_2,q_2)\}$$

Podemos ampliar la relación aun más considerando el efecto transitivo de las transiciones $\epsilon$, es decir, formamos en un primer paso

$$T_2=\{(q,p)\;\vert\;\exists r\in Q\;:\;(q,r),(r,p)\in T_0\cup T_1 \mbox{ y } (q,p)\notin T_0\cup T_1\}$$

y con eso

$$T=T_0\cup T_1 \cup T_2$$

en el ejemplo tenemos

$$T_2=\{(q_0,q_2)\}$$

y así sucesivamente

$$T_i=\{(q,p)\;\vert\;\exists r\in Q\;:\;(q,r),(r,p)\in \bigcup_{j=0}^{i-1} T_j \mbox{ y } (q,p)\notin \bigcup_{j=0}^{i-1} T_j\}$$

Finalmente definimos

$$T^*=T_0\cup T_1\cup T_2 \cup \dots = \bigcup_{i=0}^\infty T_i$$

como clausura (o ciero, o cerradura) transitiva de la relación de las transiciones $\epsilon$ o más breve clausura-$\epsilon$.

El proceso termina en nuestro caso de autómatas finitos, es decir, la unión va solamente sobre un número finito de $i$s, porque $T^*$ sigue siendo un subconjunto del conjunto finito $Q\times Q$ ($T^*Q\times Q$).

Con la clausura-$\epsilon$ podemos definir la clausura-$\epsilon$ de un estado, como todos aquellos estados que se puede alcanzar con caminos de transisiones $\epsilon$, es decir

$$cl(q)=\{p\;\vert\;(q,p)\in T^*\}$$

En el ejemplo:

$$\begin{eqnarray*} cl(q_0) &=& \{q_0,q_1,q_2\}\\ cl(q_1) &=& \{q_1,q_2\}\\ cl(q_2) &=& \{q_2\} \end{eqnarray*}$$

• hemos añadido $q_0$ a los estados finales $F$ porque existe un estado final que pertenece a la clausura-$\epsilon$ de $q_0$, es decir, $\epsilon\in L$
• hemos marcado las aristas de la clausura-$\epsilon$ con símbolos del alfabeto

Entonces podemos formalizar el lenguaje aceptado por un AFND-$\epsilon$ (parecido a lo que hicimos para un AFND).

Primero definimos la ampliación de $\delta$ para autómatas con transiciones $\epsilon$. $\delta^*(q,w)$ va a ser el conjunto de estados (igual como en el caso de $\delta^*$ para AFNDs) que podemos alcanzar desde $q$ leyendo la palabra. Entonces:

$$\delta^*: Q\times \mbox{$\Sigma^*$}\longrightarrow {\cal P}(Q)$$

1. 
   
   $$\delta^*(q,\epsilon)=cl(q)$$
   
   
   es decir, nos quedamos en la clausura-$\epsilon$ si hemos alcanzado el final de la palabra

2. $$\begin{eqnarray*} \delta^*(q,w\sigma) &=& \{ p \;\vert\;p\in Q \mbox{ y } \ex... ...ma)) \} \\ &=& \bigcup_{r\in\delta^*(q,w)}cl(\delta(r,\sigma)) \end{eqnarray*}$$
   
   
   es decir, $\delta^*(q,w)$ es el conjunto de estados alcanzables desde un estado $r$ siendo miembro de la clausura-$\epsilon$ de un estado alcanzable desde $q$ sin haber leído el último símbolo $\sigma$.

$\delta^*(q_0,w)$ enumera entonces todos los estados alcanzables desde $q_0$ leyendo la palabra $w$.

Observa: Hemos dado una definición recursiva desde la izquierda, es decir, añadimos un símbolo a la derecha. Hubiese sido posible definir $\delta^*$ para un AFND de la misma manera.

Un autómata no-determinista con transiciones $\epsilon$ $M$ acepta una palabra $w$ sobre el alfabeto $\Sigma$ ( $w\in\mbox{$\Sigma^*$}$) si

$$\delta^*(q_0,w)\cap F\not= \emptyset$$

donde $\delta^*$ sea la ampliación de la funciòn $\delta$ dada arriba.

El lenguaje aceptado por $M$ es (como siempre)

$$L(M) = \{ w \;\vert\;M \mbox{ acepta } w \}$$