Por el Teorema de Kleene sabemos que tanto Expresiones Regulares (una relajación en la notación de los Lenguajes Regulares) son equivalentes a los Autómatas Finitos (no determinístico). El que sean equivalentes quiere decir que representan exactamente al mismo tipo de lenguajes, los Lenguajes Regulares. Este es una característica muy importante de nuestro modelo computacional.

Esta correspondencia tiene varias implicaciones:

• Si sabemos de un Lenguaje Regular L está garantizado que debe existir un autómata finito.
• Si sabemos sobre un Autómata Finito A está garantizado que debe existir un Lenguaje Regular y por lo tanto una Expresión Regular que los represente.

¿Cúal es la diferencia en ER y Autómata? #

¿Si ambos ER y Autómatas representan el mismo tipo de lenguajes porque necesitamos a ambos, porque no quedarnos con una de la opciones? La respuesta tiene que ver con que ER y AF son dos aspectos diferentes de los Lenguajes Regulares. Las Expresiones Regulares especifican el patrón que debe seguir las cadenas que pertenecen al lenguaje, mientras que el Autómata Finito define el proceso que se tiene que seguir para aceptar a una cadena del lenguaje.

Ejemplo de especificación vs proceso #

Supongamos el lenguaje de las cadenas conformadas por aes y bes en donde todas las cadenas contiene la subcadena abb.

La ER que representa a este lenguaje es \((a+b)^*abb(a+b)*\) . Si nos detenemos a analizar esta ER podemos ver que nos está especificando la forma que tienen que ser las cadenas, nos dice que puede venir cualquier cosa \((a+b)^*\) , es decir cualquier cadena compuesta por repeticiones de aes o bes. Sin embargo, en algún momento debe aparecer la cadena abb para después ser seguida por cualquier cosa. El infijo de abb garantiza que nuestra cadena tenga esa subcadena, no nos dice nada de cómo será procesada, por ejemplo con la cadena abbabb no queda claro cual de las dos apariciones de abb se alinea con el infijo.

Por otro lado un autómata para este lenguaje es:

Se puede apreciar que el autómata sigue una estrategia diferente, describe una secuencia de decisiones para determinar si en la cadena ya ocurrió la subcadena abb; al comenzar si viene una be no hay chances de que ocurra la cadena abb, pero si viene una a potencialmente hemos encontrado la a de la subcadena, sin embargo si llega otra a quiere decir que la a pasada no pertenece a nuestra subcadena ya que el patrón aa no es el que buscamos confirmar; sin embargo la nueva a podría ser el inicio de nuestro patrón abb; si llega una b se confirmaría que llevamos dos símbolos de nuestro patrón, sólo faltará una siguiente b y podríamos estar seguros que ocurrió el patrón que buscábamos y después de eso ya no importa lo que llegue, siempre estaremos en un estado final. Sin embargo, si llegaba una a se rompe el patrón y tenemos que regresar a considerar que el patrón buscado apenas está comenzado con esa nueva a, por eso regresamos al estado q_1 en lugar que el inicial.