Aceptor de Estado Finito

Un aceptor de estado finito es un tipo de Autómata de Estado Finito $M=(Q,S,P,I,F)$ donde:

• $I\subseteq Q$ son los estados iniciales.
• $F\subseteq Q$ son los estados finales.
• $P\subseteq Q\times S\times Q$ es la relación de transición de $M$. Puede tener un comportamiento no determinístico.
• Si $(q,s,q^{\prime })\in P$ entonces se da $q\stackrel{s}{\to }{q}^{\prime }$ que es una transición de $M$.

$M$ acepta un string $\omega \in S\ast ⟺:q\stackrel{\omega }{⟹}{q}^{\prime }$ para algún $q\in I$ y algún $q^{\prime }\in F$. El lenguaje reconocido por $M$ es $L(M)=\{\omega \in S\ast /q\stackrel{\omega }{}⟹q^{\prime };q\in I;q^{\prime }\in F\}$.

Si las transiciones $P$ de $M$ constituyen una función $P:Q\times S\to Q$ y si $M$ tiene exactamente un estado inicial, $M$ es un aceptor de estados finitos determinístico.

Conversión a Aceptores Determinísticos

Podemos imaginar que la $M$ en cierto instante ante cierta entrada se encuentra en cierta combinación de estados.

Dado el AEF no determinístico $M_n=(Q_n,S,P_n,I_n,F_n)$ se construye el AEF determinístico $M_d=(Q_d,S,P_d,I_d,F_d)/L(M_n)=L(M_d)$. Sea $X_{[\omega ]}=\{q^{\prime }\in Q_n/q\stackrel{\omega }{}⟹q^{\prime }\text{ para alguˊn }q\in I_n\}$ el conjunto de los estados alcanzables de $M_n$ para el string de entrada $\omega$. Para $\lambda :X_{[\lambda ]}=I_n$.

Dado $X_{[\varphi ]}$ se tiene $X_{[\varphi s]}=\{q^{\prime }\in Q_n/q^{\prime \prime }\stackrel{s}{\to }{q}^{\prime }\text{ para alguˊn }{q}^{\prime \prime }\in X_{[\varphi ]}\}$ por lo que $X_{[\varphi s]}$ solo depende de $X_{[\varphi ]}$ y de $s\in S$.

El número de conjuntos alcanzables $X_{[\omega ]}$ distintos es finito y $X_{[\omega ]}\subseteq Q_n$. Los $I_d$ de $M_d$ corresponden a los $X_{[\omega ]}$ que contienen estados finales de $M_n$. $I_n=X_{[\lambda ]}⟹I_d=\{X_{[\lambda ]}\}$.

$F_d=\{X\in Q_d/X\cap F_n\ne \varphi \}$ son los conjuntos alcanzables que tienen un $q_F\in F_n$.

El estado $X^{\prime }$ es s-sucesor de $X$ en $M_d$ sí y solo sí $X^{\prime }$ consiste de los s-sucesores en $M_n$ de $X$: $X\stackrel{s}{\to }{X}^{\prime }\text{ en }{M}_d⟺X^{\prime }=\{q^{\prime }/q\stackrel{s}{\to }{q}^{\prime }\text{ en }{M}_n\text{ para }q\in X\}$.

Teorema

Por cada AEFND $M_n$ se puede construir un AEFD $M_d$ tal que $L(M_d)=L(M_n)$.

AEF con Transiciones Lambda

Un AEF-$\lambda$ es un aceptor de estados finitos no determinístico $M=(Q,S,P,I,F)$ en el que $P:Q\times (S\cup \{\lambda \})\to \delta (Q)$.

Equivalencia entre AEF-$\lambda$ y AEFND

Teorema

Dado un AEF-$\lambda$ se puede construir un AEFND equivalente tal que $L(M)=L(M^{\prime })$.

Sea $\lambda [q]=\{q\}\cup \{q^{\prime }\in Q/q\stackrel{\lambda }{\to }\dots \stackrel{\lambda }{\to }{q}^{\prime }\text{ en }M\}$ o $\lambda [q]=\{q\}\cup \lambda [q^{\prime }]\forall q^{\prime }\in P(q,\lambda )$. Nótese que generalmente $\lambda [q]\ne P(q,\lambda )$.

Por definición: $q\in \lambda [q]⟹\lambda [\varphi ]=\varphi ;\lambda [\{q_1,\dots ,q_k\}]=\lambda [q_1]\cup \cdots \cup \lambda [q_k]$.

Procedimiento de construcción: sea $M^{\prime }=(Q,S,P^{\prime },I,F^{\prime })$ donde $P^{\prime }:Q\times S\to \delta (Q)$ es tal que $P^{\prime }(q,s)=\lambda [P(\lambda [q],s)]$. Así, $M^{\prime }$ simula todas las transiciones $\lambda$ de $M$ teniendo en cuenta todos los posibles caminos. Se obtiene $F^{\prime }=\{q\in Q/\lambda [q]\cap F\ne \varphi \}$. Los estados de aceptación de $M^{\prime }$ incluye los de $M$ y los $q$ que llegan a un $q_F$ con transiciones $\lambda$.