Pasos para convertir un automata a Expresion Regular (ER)

La exprecion regular es una representacion matematica de un automata. 

Concatenacion de cadenas:

Sean x e y dos cadenas, Entonces , xy denota la concatencacion de x e y, es decir, la cadena formada por una copia de x seguida de una copia de y.

Entonces para convertir un automata a Expresión Regular se deben seguir los siguientes pasos.

Paso Numero Uno:

Se representa los estados de manera matematica, tambien representando el estado de acceptacion con el simbolo de epsilon(Ɛ)

Tomando en cuenta que el siguiente simbolo se refiere a la concatenacion "|". Asi que al final la lo representariamos de la siguiente manera.

q0 = 1q0 | 0q1Ɛ Transformandose a q0 = 1q0 + 0q1Ɛ

q1 = 1q1Ɛ | 0q0 Transformandose a q1 = 1q1Ɛ + 0q0

Paso Numero Dos:

En cada ecuacion se remplasa el estado que se repita con la estrella de keleen(*) quedando las ecuaciones de la sguiente manera.

q0 = 1* + 0q1Ɛ

q1 = 1*Ɛ + 0q0

Paso Numero Tres:

Se ordena y resuelve las ecuacciones de abajo hacia arriba al mismo tiempo se quita el simbolo de epsilon pues es la representacion de nada. Viendose de la siguiente manera

q1 = 1* + 0q0

q0 = 1* + 01* + 0q0   Remplasando asi a q1 puesto a que ya lo teniamos resulte anteriormente. Siendo

esta nuesta expresión regular sin resolver

Paso Numero Cuatro:

A la segunda ecuacion se le vuelve a remplasar el estado que se repite quedando de la siguiente manera.

q0 = 1* + (01* + 0)*  Siendo esta nuestra Expresión Regular ya resuelta que representa nuestro automata.