e-AFI a AFD
Ahora queremos mostrar que el lenguaje reconocido por un autómata con transiciones vacías también puede ser realizado por un autómata no determinista sin transiciones vacías (determinación e-AFI hacia AFD). Esta operación requerirá la adición de nuevas transiciones en el autómata.
Cualquier idioma reconocido por un AFN con transiciones ε puede ser reconocido por un AFN (sin transiciones ε) que tiene el mismo número de estados.
Construcción del AFN equivalente a un autómata con ε - transiciones, prolongando δ en δ1 (el cierre transitivo son todos los estados que puede alcanzar un estado mediante una transición dada).
Primer paso: Adición de ε - transiciones por cierre transitivo.
Para todos los estados q accesibles desde p por ε-transición (en varios pasos), agregamos una ε - transición directa de p a q. Extendemos así la función δ: δ1 (p, ε) = todos los estados accesibles desde p por ε - transición.
Segundo paso: adición de transiciones adicionales y estados iniciales adicionales, luego eliminación de transiciones ε.
Los estados iniciales son todos los estados accesibles desde los estados iniciales por ε - transición.
Para cualquier transición de p a q por una letra, agregamos transiciones de p a r con la misma letra para todas las ε - transiciones de q a r: δ1 (p, a) = δ (p, a) ∪ (∪q∈δ (p, a) δ1 (q, ε)).
Eliminamos todas las ε - transiciones
Ejemplo
El principio del algoritmo consiste en reemplazar cada camino de longitud 1 que comienza con una transición épsilon por una nueva transición que describe este camino.
Hay dos caminos de longitud 1 que comienzan con la transición en épsilon:
- (1, ε, 3) (3, b, 3)
- (1, ε, 3) (3, c, 4)
Agregamos al autómata dos nuevas transiciones que resumen estos dos caminos:
- (1, b, 3)
- (1, c, 4)
Y eliminamos la transición (1, ε, 3).
El algoritmo es un poco más complejo en los casos en los que se suceden varias transiciones épsilon y si pasan a un estado final, pero el principio general aquí presentado sigue siendo válido (basta con aplicar el primer paso).
El uso de transiciones épsilon a veces hace posible describir un idioma con mayor claridad. También permite simplificar la descripción de ciertas operaciones (por ejemplo la unión o la concatenación -> ver autómata de thompson).
La existencia de transiciones épsilon hace que el autómata no sea determinista, ya que siempre tenemos la posibilidad de tomar prestada dicha transición incluso cuando hay una transición ordinaria que podríamos tomar prestada.
Otro ejemplo
Considere el siguiente autómata:
Para ello, primero es necesario calcular, para cada estado, los ε-sucesores de cada estado p, es decir el conjunto de estados q tal que exista un camino formado solo por ε-transiciones partiendo de p llegando en q.
Calculamos los ε-sucesores de cada estado: Succε (p) = {q, r}, Succε (q) = {r}, Succε (r) = ∅.
Obtenemos la siguiente NFA:
A continuación, puede determinarlo con el método de NFA a DFA, o puede determinarlo directamente en su forma con la transición de espilon como en el siguiente ejemplo.
Tomemos el autómata y transformémoslo en un DFA:
El primer paso consiste en calcular el cierre épsilon para cada estado de este autómata:
| Delta (Q) | Para | B | Cierre -> Q ' |
| pag | pag | – | {p, q, r} |
| q | – | q | {q, r} |
| r | r | – | {r} |
Para cada estado del cierre, calculamos sus transiciones en el alfabeto sin épsilon:
| Delta (Q ') | Para | B |
| {p, q, r} | {p, r} | {q} |
| {q, r} | {r} | {q} |
| {r} | {r} | – |
Para cada estado obtenido por las transiciones, calculamos el cierre:
| Delta (Q ') | Para | B |
| {p, q, r} | {p, r} -> {p, q, r} | {q} -> {q, r} |
| {q, r} | {r} -> {r} | {q} -> {q, r} |
| {r} | {r} -> {r} | – |
Denotar por {p, q, r} = P; {q, r} = Q y {r} = R. Obtenemos el siguiente autómata:
ES 
FR 
EN