Cómo convertir un autómata finito en la expresión regular

autómatas finitos (FA - autómatas finitos) pertenecen a un modelo matemático capaz de reconocer cadenas de idiomas regulares. El estudio de la FA es una parte importante de los fundamentos de la teoría de la computación. El modelo puede generar lenguajes regulares cadenas son expresiones regulares (RE - Expresiones Regulares) (el mismo utilizado en varios lenguajes de programación como Java). Ahora, vamos a aprender cómo convertir una FA en un RE.

pasos

Comience por crear una FA o el uso de un suministra como ejercicio. La figura FA servirá como un ejemplo.

El procedimiento consiste en eliminar uno por uno los estados de FA, sustituyendo el estado retirado por las nuevas transiciones cuyas etiquetas son las etiquetas de las transiciones de todos los posibles caminos a través de ese nodo.

Elija uno de los estados de "colapso". En nuestro ejemplo, q2 fue escogido.

Comprobar cuáles son los posibles caminos a través de ese nodo. Crear nuevas transiciones que unen los estados restantes como se describe anteriormente. En el ejemplo, vamos a crear una transición que conecta q0 la q1 con la etiqueta 00 es de q0 la q3 con la etiqueta 01.

Imagen titulada El autómata sin el Q2 Estado

Compruebe el nuevo autómata si las nuevas transiciones realmente representan los caminos retirados.

Elige un nuevo estado de quitar.

Elige otro estado para eliminar. En el ejemplo, ahora quitar q3.

Una vez más crear nuevas transiciones que representan los caminos a través de ese estado. una transición ha sido creado entre q0 y q4 con la etiqueta 001 y desde q1 y q4 con la etiqueta 01.

La imagen titulada q1 proceso de eliminación

A veces es necesario para representar trayectorias circulares mediante el operativo cierre de Kleene (* - asterisco) y hacer los pasos intermedios. En la figura, los caminos entre q0 y q4 quien falleció q1 Ellos se convirtieron a las transiciones.

Imagen titulada conversión completado. Nótese la expresión regular simplificada ya continuación

Continuar para eliminar los estados, hasta que sólo alrededor de un estado inicial y un estado final. Escriba la expresión regular que representa los vínculos con las operaciones de cierre.

La expresión regular ((00 + 1) (1 * 01) 001) (01 * 01) *

consejos

Trate de obtener los estados que tienen el menor número de maneras. Puede haber una explosión combinatoria si intenta quitar un estado muy "activo" antes.
A veces, las expresiones regulares resultantes pueden parecer muy compleja. Y la mayoría de las veces se pueden simplificar.
El JFLAP puede convertir en FA RE automáticamente. De ello se desprende otro método (usando transiciones lambda) a, y que genera no están optimizados.