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.
Nótese 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 un palabra (de longitud 1 o 0), y 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 autómata con transición vacía a palabras reconocidas
El proceso es el mismo que el árbol creado por un autómata no determinista. Tenga en cuenta que además de tener que crear nuevas ramas en caso de indeterminismo, también es necesario atravesar las transiciones de los estados sucesores por epsilon-transition.
Si tomamos el autómata de arriba en 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 autómata con transición épsilon, entonces es necesario cerrar el autómata.
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).
