Autómata finito no determinista

Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En este ejemplo, δ(q₀,b)=q₀ y δ(q₀,b)=q₁. Por lo tanto, se trata de un autómata finito no determinista, que reconoce la expresión regular (a|b)*b⁺.

En un AFND puede darse cualquiera de estos dos casos:

• Que existan transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
• Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.

Definición formal

Formalmente, si bien un autómata finito determinista se define como una 5-tupla (Q, Σ, q₀, δ, F) donde:^[1]​

• ${\displaystyle Q\,}$  es un conjunto de estados;
• ${\displaystyle \Sigma \,}$  es un alfabeto;
• ${\displaystyle q_{0}\in Q}$  es el estado inicial;
• ${\displaystyle \delta \colon Q\times \Sigma \to Q}$  es una función de transición;
• ${\displaystyle F\subseteq Q}$  es un conjunto de estados finales o de aceptación.

en un AFND la función de transición se define como:

${\displaystyle \delta :Q\times \Sigma \to {\mathcal {P}}(Q)}$ 

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

${\displaystyle \delta :Q\times \{\Sigma \cup \epsilon \}\to {\mathcal {P}}(Q)}$ 

donde P(Q) es el conjunto potencia de Q. Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).

La interpretación que se suele hacer en el cómputo de un AFND es que el automáta puede pasar por varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Asimismo, en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial.

Funcionamiento

La máquina comienza en el estado inicial especificado y lee una cadena de caracteres pertenecientes al alfabeto. El autómata utiliza la función de transición de estados T para determinar el siguiente estado, usando el estado actual y el símbolo que acaba de leer o la cadena vacía. Sin embargo, "el estado siguiente de un AFND no solo depende de el evento de entrada actual, sino que también en un número arbitrario de los eventos de entrada posterior. Hasta que se producen estos acontecimientos posteriores no es posible determinar en qué estado se encuentra la máquina" . Cuando el autómata ha terminado de leer, y se encuentra en un estado de aceptación, se dice que el AFND acepta la cadena, de lo contrario se dice que la cadena de caracteres es rechazada. Tanto para un AFND como para un autómata finito determinista (AFD) se puede aceptar el mismo lenguaje. Por lo tanto, es posible convertir un AFND existente en un AFD para el desarrollo de una máquina tal vez más simple. Esto puede llevarse a cabo utilizando la construcción del conjunto potencia, que puede conducir a un aumento exponencial en el número de estados necesarios.

Implementación

Hay muchas formas de implementar una AFND:

• Convertir al equivalente AFD: en algunos casos esto puede causar un aumento exponencial en el tamaño del autómata, y así un espacio auxiliar proporcional al número de estados en el AFND (como el almacenamiento del valor del estado requiere en la mayoría de un bit por cada estado en el AFND).

• Mantener un conjunto de datos de todos los estados en que la máquina podría estar en la actualidad. Al consumir el último carácter de entrada, si uno de estos estados es un estado final, la máquina acepta la cadena. En el peor de los casos, esto puede requerir espacio adicional proporcional al número de estados en el AFND; si la estructura del conjunto usa un bit por estado del AFND, entonces esta solución es exactamente equivalente a la anterior.

• Crear múltiples copias. Por cada n forma de la decisión, el AFND crea hasta n-1 copias de la máquina. Cada uno de ellos entrara en un estado independiente. Si, al momento de consumir el último símbolo de la entrada, al menos una copia del AFND esta en un estado de aceptación, el AFND lo aceptará. (Esto también requiere un almacenamiento lineal con respecto al número de estados del AFND, ya que puede haber una máquina por cada estado del AFND).

AFND-ε

Propiedades

Para todo ${\displaystyle p,q\in Q,}$ , se escribe ${\displaystyle p{\stackrel {\epsilon }{\rightarrow }}q}$  si y solo si a ${\displaystyle q}$  se puede llegar desde ${\displaystyle p}$ , yendo a lo largo de cero o más flechas ${\displaystyle \epsilon }$ . En otras palabras, ${\displaystyle p{\stackrel {\epsilon }{\rightarrow }}q}$  si y solo si existe ${\displaystyle q_{1},q_{2},\cdots q_{k}\in Q}$  donde ${\displaystyle k\geq 0}$  tal que

${\displaystyle q_{1}\in T(p,\epsilon ),q_{2}\in T(q_{1},\epsilon ),\cdots q_{k}\in T(q_{k-1},\epsilon ),q\in T(q_{k},\epsilon )}$ .

Para cualquier ${\displaystyle p\in Q}$ , el conjunto de estados a los que se puede llegar a partir de p se le llama epsilon-closure o ε-closure de p y se escribe como

${\displaystyle \,E(\{p\})=\{q\in Q:p{\stackrel {\epsilon }{\rightarrow }}q\}}$ .

Para cualquier subconjunto ${\displaystyle P\subseteq Q}$ , definir el ε-closure de P como

${\displaystyle E(P)=\bigcup \limits _{p\in P}E(\{p\})}$ .

Para el conjunto vacío

${\displaystyle E(\{\})=\{\}}$ .

Para cualquier subconjunto ${\displaystyle A\subseteq Q}$  y ${\displaystyle B\subseteq Q}$  se cumplen las propiedades:

${\displaystyle E(E(A))=E(A)}$ .

Si ${\displaystyle A\subseteq B}$  entonces ${\displaystyle E(A)=E(B)}$ .

${\displaystyle E(A\cup B)=E(A)\cup E(B)}$ .

Las transiciones epsilon son transitivas, ya que puede demostrarse que para todo ${\displaystyle q_{0},q_{1},q_{2}\in Q}$  y ${\displaystyle P\subset Q}$ , si ${\displaystyle q_{1}\in E(\{q_{0}\})}$  y ${\displaystyle q_{2}\in E(\{q_{1}\})}$ , entonces ${\displaystyle q_{2}\in E(\{q_{0}\})}$ .

Del mismo modo, si ${\displaystyle q_{1}\in E(P)}$  y ${\displaystyle q_{2}\in E(\{q_{1}\})}$  entonces ${\displaystyle q_{2}\in E(P)}$  Sea x una cadena del alfabeto Σ∪{ε}. Un AFND-ε M acepta la cadena x si existe tanto una representación de x de la forma x₁x₂ ... x_n, donde x_i ∈ (Σ ∪{ε}), y una secuencia de estados

p₀,p₁, ..., p_n, donde p_i ∈ Q, Cumpliéndose las siguientes condiciones:

1. p₀ ${\displaystyle \in }$  E({q₀})
2. p_i ${\displaystyle \in }$  E(T(p_i-1, x_i )) para i = 1, ..., n
3. p_n ${\displaystyle \in }$  F.

Sea ${\displaystyle P\subseteq Q}$ , la definición recursiva de ${\displaystyle E(P)}$  es:

1. ${\displaystyle \forall q\in P\Rightarrow q\in E(P)}$ 
2. ${\displaystyle \forall q\in E(P)\land \forall p\in T(q,\epsilon )\Rightarrow p\in E(P)}$ 

Para calcular ${\displaystyle E(P)}$  :

definiremos ${\displaystyle E(P)=B_{n}}$  donde

1. ${\displaystyle B_{0}=P}$ 
2. ${\displaystyle B_{i}=B_{i-1}\cup \{p/q\in B_{i-1}\land p\in T(q,\epsilon )\}}$ 

Si ${\displaystyle B_{i}=B_{i-1}\Rightarrow B_{n}=B_{i-1}}$ 

Aplicación

El AFND y el AFD son equivalentes en esto, ya que si un lenguaje es reconocido por el AFND, también será reconocido por un AFD, y viceversa. El establecimiento de esta equivalencia es útil porque a veces la construcción de un AFND para reconocer un lenguaje determinado es más fácil que construir un AFD para dicho lenguaje. También es importante porque el AFND se puede utilizar para reducir la complejidad del trabajo matemático necesario para establecer muchas propiedades importantes en la teoría de la computación. Por ejemplo, es mucho más fácil demostrar las siguientes propiedades utilizando un AFND que un AFD:

• La unión de dos lenguajes regulares es regular.
• La concatenación de dos lenguajes regulares es regular.
• La Clausura de Kleene en un Lenguaje regular es regular.

Ejemplo

El ejemplo siguiente muestra un AFND M, con un alfabeto binario que determina si la entrada contiene un número par de ceros (0) o un número par de unos (1). Entonces M = (Q, Σ, T, s₀, F) donde:

• Σ = {0, 1},
• Q = {s₀, s₁, s₂, s₃, s₄},
• E({s₀}) = { s₀, s₁, s₃ }
• F = {s₁, s₃}, y
• La función de transición T puede ser definida por esta tabla de transición de estados:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

El diagrama de estados para M es:

 

M puede ser visto como la unión de dos AFDs: uno con los estados {S₁, S₂} y el otro con los estados {S₃, S₄}.

El lenguaje de M puede ser descrito por el lenguaje regular dado por la expresión regular:

${\displaystyle (1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})}$ 

Véase también

• Autómata finito
• Autómata finito determinista
• Construcción de subconjuntos

Referencias

1. Chakraborty, Samarjit (17 de marzo de 2003). «Formal Languages and Automata Theory. Regular Expressions and Finite Automata». Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich (en inglés): 17. Consultado el 30 de marzo de 2010. 

Bibliografía

• M. O. Rabin and D. Scott, "Finite Automata and their Decision Problems", IBM Journal of Research and Development, 3:2 (1959) pp.115-125.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979.

•   Datos: Q617295
•   Multimedia: Finite state machine