PLC con transición vacía
Estamos acostumbrados a dibujar un autómata con transición vacía, representando los estados con círculos, indicando el estado inicial con una flecha de entrada, los estados de aceptación con un doble círculo o una flecha de salida, y la transición del estado q al estado q' leyendo la letra α con una flecha que va de q a q' y está etiquetada con α.
Un autómata finito A con transición épsilon (o autómata con transición vacía) es un triplete (Vt, Q, T) donde
- Vt es el vocabulario del autómata;
- Q es el conjunto finito de estados del autómata;
- T: Q × (Vt ∪ ε) → Q, es un mapa parcial llamado función de transición del autómata.
Tenga en cuenta que la notación q (α) → q 'se vuelve ambigua, ya que ahora toma dos significados diferentes dependiendo de si α se considera como una letra (o como el símbolo ε) y entonces habrá una sola transición, o como una palabra. (de longitud 1 o 0), y entonces puede haber un número arbitrario de transiciones (de las cuales como máximo una no estará vacía).
Una vez más, las nociones de derivación no han cambiado, y la de árbol de derivación
requiere solo una adaptación trivial, ya que ahora hay transiciones etiquetadas por ε. Los cálculos de un autómata con transiciones vacías permiten el paso a través de cualquier número de transiciones vacías durante la ejecución. Por lo tanto, el número de estados escaneados ya no será igual al número de letras de la palabra de entrada, sino que puede ser mucho mayor. El árbol de cálculo de un autómata con transiciones vacías resulta ser una herramienta menos interesante que para los autómatas no deterministas sin transiciones vacías.
De PLC con transición vacía a palabras reconocidas
El proceso es el mismo que el del árbol creado por un autómata no determinista. Notemos que además de tener que crear nuevas ramas en caso de indeterminismo, también es necesario pasar por las transiciones de los estados sucesores por épsilon-transición.
Si tomamos el autómata anterior sobre la palabra aaaab:
p (aaaab) → q (aaab) → r (aaab) → s (aaab) → s (aab) → s (ab) → s (b) → q (b) → r - estado terminal
Es complejo calcular las palabras de longitud n reconocidas por un PLC con transición épsilon, entonces es necesario cerrar el PLC.
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).
ES 
FR 
EN