Algoritmo de Brzozowski y McCluskey

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 de autómatas

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 a través de este estado (a un estado adyacente). El idioma reconocido por esta ruta se agrega luego al PLC 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 como resultado el lenguaje a², por lo que se agrega a la ruta q0 -> q3. La ruta q3 -> q2 -> q3 da el lenguaje 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.