Pasos para convertir un autómata a ER

Algoritmo

1. Se observa el autómata y se analiza estado por estado

2.Convertir cada estado en una ecuación siguiendo los pasosos siguientes.

3. Escribir el estado inicial 

ej. Si se toma el estado q0 :

q0 

ej. Si se toma el estado q1 :

q1 

4. Igualar

ej. Si se toma el estado q0 :

q0 = 

ej. Si se toma el estado q1 :

q1 =

5. Observar las palabras que tiene 

Σ={0,1}

6. Dependiendo del estado que va a tomar se escribe la palabra y el nombre del estado, si el estado se repite se utiliza la estrella de Kleene.

   Nota: se le agrega el símbolo landa  λ cuando llega al estado de aceptación para representar que puede tomar el alfabeto vacío. Al representar la ecuación con la estrella de Kleene ya no se utiliza el símbolo de Landa.

ej. Si se toma el estado q0 :

q0 =1q0      ó       q0=1* 

ej. Si se toma el estado q1 :

q1=1q1λ     ó     q1=1*

7. Luego se concatena utilizando  | ó +

ej. Si se toma el estado q0 :

q0 =1q0 |     ó       q0=1* + 

ej. Si se toma el estado q1 :

q1=1q1λ |       ó     q1=1*+ 

8. Dependiendo del estado que va a tomar se escribe la palabra y el nombre del estado

ej. Si se toma el estado q0 :

q0 =1q0 |  0q1λ     ó       q0=1* + 0q1

ej. Si se toma el estado q1 :

q1=1q1λ | 0q0      ó     q1=1*+ 0q0

9. Ya  que tengo las ecuaciones se resuelve de abajo hacia arriba. ↑

 2)       q0=1* + 0q1    

 1)       q1=1* +0q0   

La primera ecuación pasa igual. 

1)      q1=1* +0q0   

2)      q0=1* + 0(1* + 0q0)  ➡Como ya tenemos el valor de q1 se sustituye en vez de volver a poner q1.

  q0=1* + 0(1* + 0q0)    Expresión regular