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 que se suceden varias transiciones épsilon y si van a un estado final, pero el principio general presentado aquí sigue siendo válido (solo aplica el primer paso).
El uso de transiciones épsilon a veces permite describir un idioma de manera más legible. También permite simplificar la descripción de ciertas operaciones (por ejemplo, unión o concatenación -> ver autómata de Thompson). thompson).
La existencia de transiciones épsilon hace que el autómata no sea determinista, ya que uno siempre tiene la posibilidad de tomar prestada tal transición, incluso cuando existe una transición ordinaria que uno podría 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:
