reseña

Equivalencia entre autómatas finitos

Para un lenguaje dado no existe un autómata finito único que lo acepte

Definición
Dos autómatas M1 y M2 son equivalentes M1M2 cuando aceptan el mismolenguaje.

Ejemplo:- Cadenas de a’s sobre {a,b} : a*











La demostración de equivalencias de dos autómatas se convierte en la demostración de igualdad de los lenguajes que seaceptan. Si los lenguajes son infinitos, esto se complica

Teorema de Moore
Existe un algoritmo para decidir si dos autómatas son equivalentes o no.

Este algoritmo consiste en la construcciónde una tabla de comparación de autómatas. Esta tabla permite convertir el problema de los lenguajes aceptados en un problema de comparación de estados de los autómatas


Definición
Dos estados q yq’ son compatibles si ambos son finales o ninguno de los dos es final. En caso contrario, son estados incompatibles.

La idea es: Averiguar si existe alguna secuencia de caracteres w tal quesiguiendo simultáneamente en los dos autómatas se llega a estados incompatibles. Si dicha secuencia no existe, entonces los autómatas son equivalentes.

Para lograrlo, se crea una estructura, la “tablade comparación” que consta de  + 1 columnas y se construye de la siguiente manera:


1. Inicialmente se anota en la columna 0 un par ordenado(s,s’) que contiene los estados iniciales de M y M’respectivamente.

1. Si en la columna 0 hay un par (r,r’), en las columnas 1 a  + 1 se escriben los pares (rx,r’x) de estados a los que se llega a partir de (r,r’) por medio de transiciones con elsímbolo x

1. Cada par (rx,r’x) generado en el punto 2 que no aparezca en la columna 0 se anota ahí.

1. Si aparece en la columna 0 un par (r,r’) tal que r es un estado final y r’ no los es, oviceversa, se interrumpe la construcción de la tabla, concluyendo que los dos autómatas no son equivalentes. En caso contrario se continua a partir del paso 2.

1. Si no aparecen nuevos pares...