Algoritmo de Brzozowski y McCluskey
El algoritmo de Brzozowski y McCluskey hace un uso intensivo de la representación gráfica del autómata. El autómata mismo es generalizado, permitiendo, como etiquetas de transición, no solo letras, sino expresiones regulares. A partir de un autómata terminado, eliminamos progresivamente los estados, y al final, terminamos con un autómata que tiene una sola transición. La etiqueta de esta transición es una expresión regular para el lenguaje reconocido por el autómata.
Un autómata generalizado se define como un autómata finito no determinista tradicional, con las siguientes peculiaridades:
- tiene solo un estado inicial α y solo un estado final ω
- las transiciones están etiquetadas con expresiones regulares
- ninguna transición entra en α y ninguna transición sale del estado final ω.
Podemos transformar fácilmente un autómata ordinario PARA en un autómata generalizado: basta con sumar los estados α y ω y ε-transiciones de α a los estados iniciales de PARA, y ε-transiciones de los estados terminales de PARA a ω.
Reducción del autómata
Dado un autómata generalizado, calculamos un autómata generalizado que tiene menos transiciones o estados, aplicando las transformaciones siguientes sin modificar el lenguaje reconocido. Al final, solo existen los dos estados α y ω y una transición de α y ω cuya etiqueta es una expresión regular que denota el lenguaje reconocido. Las transformaciones son reducciones en las transiciones y reducciones en los estados.
Para reducir un estado, se deben realizar todos los caminos que pasan por este estado (hacia un estado adyacente). El lenguaje reconocido por este camino se agrega luego al autómata reducido (ver el ejemplo).
El siguiente ejemplo muestra las principales reducciones posibles así como las expresiones regulares generadas en el autómata:
Lo que da el siguiente autómata generalizado:
Eliminamos q2: la ruta q0 -> q2 -> q3 da el idioma a², por lo tanto se agrega a la ruta q0 -> q3. La ruta q3 -> q2 -> q3 da el idioma ba o (ba)* porque es un bucle en q3 -> q3
Eliminamos q1: aquí el bucle en q1 dará un a *
Eliminamos q0:
Eliminamos q3:
Nótese que la expresión obtenida también depende del orden de eliminación, pero que todos los lenguajes generados son iguales.
