computer science - science - ¿Cómo se normaliza una máquina de estados finitos?

master of science in engineering

Question

1. ¿Cómo encuentras el mínimo determinista FSM?
2. ¿Hay alguna manera de normalizar las MFS no deterministas?
3. ¿Existe un algoritmo de límite de tiempo lineal para encontrar el FSM mínimo para una máquina determinada?
4. ¿Hay alguna manera de ver si dos FSM son equivalentes?

Esta no es una pregunta de tarea. Estaba viendo esta serie de conferencias y me puse curioso.

Answer 1

Algunas respuestas informales para darle ideas, para pruebas detalladas, lea un buen libro sobre Autómatas, por ejemplo, este o los mencionados en las otras respuestas. Y estoy bastante seguro de que hay materiales en línea que puede encontrar respondiendo a todas sus preguntas.

• ¿Cómo encuentras el mínimo determinista FSM?

El procedimiento es eliminar los estados duplicados (o combinar estados equivalentes). Sabes que el estado y las transiciones son las claves para generar cadenas. Básicamente, los estados duplicados no contribuyen a hacer que el lenguaje generado sea mayor o menor. El algoritmo comienza desde los estados finales que siempre tienen la capacidad de generar la lamda (cadena vacía), y actualizar de forma recursiva una tabla que indica la capacidad de generación de un estado, y finalmente fusionar esos estados sin hacer ninguna diferencia.

• ¿Hay alguna manera de normalizar las MFS no deterministas?

El DFA normalizado para el NFA está utilizando diferentes colecciones de los estados de NFA como estados de DFA, por ejemplo, {state0} - (1) -> {state1, state2} para eliminar la parte no determinista, no hay manera de evitar La explosión del estado como DFA tiene que hacer eso para representar el lenguaje.

• ¿Existe un algoritmo de límite de tiempo lineal para encontrar el FSM mínimo para una máquina determinada?

Recuerdo que el mejor es O (NLogN) haciendo algunos trucos de reutilización de la información en un artículo de un profesor de la Universidad de Western Ontario, y dudo que existan mejores. Creo que el clásico es O (N ^ 2).

• ¿Hay alguna manera de ver si dos FSM son equivalentes?

Sí. Obtenga el mínimo, codifique el estado por su cadena de acceso (una cadena que podría alcanzar el estado desde el estado de inicio, este es prácticamente el "nombre" real de un estado allí) y verifique el mapa de transición. Sin embargo, podría haber mejores maneras, pero no habría una gran diferencia en el bigO.

Answer 2

Como todas las FSM no deterministas tienen una FSM determinista correspondiente, la respuesta a 1 y 2 debe ser la misma.

Si desea saber más, obtenga una copia de "Introducción a la teoría de la computación" de Michael Sipser, que es un gran libro para aprender estas cosas. Sipser sabe de qué habla y cómo comunicarlo muy bien.

Answer 3

Verifique los "Fundamentos del diseño del compilador" a partir de la sección 2.5. Disponible de forma gratuita en línea. http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics_lulu.pdf

Cubre la conversión de un NFA a un DFA y minimizar el DFA. Las NFA pueden expandirse exponencialmente cuando se convierten a DFA.

"... cualquier lenguaje regular (un lenguaje que puede ser expresado por una expresión regular, NFA o DFA) tiene un DFA mínimo único. Por lo tanto, podemos decidir la equivalencia de las expresiones regulares (o NFA o DFA) al convertir ambos en DFA mínimos. y comparar los resultados ".

Answer 4

• Si le dan un FSM determinista, entonces puede encontrar uno equivalente, mínimo, usando un algoritmo bastante fácil en O (n ² ); El algoritmo de Hopcroft lo hace en O (n log n). Here encontrarás la descripción de ambos. Puede verificar si A y B son equivalentes minimizándolos y verificando si son iguales.
• Si se le da un FSM no determinista, entonces encontrar uno equivalente, es PSPACE-complete . En otras palabras, no se conoce ningún buen algoritmo y se conjetura que no existe. La verificación de la equivalencia de dos autómatas no deterministas también está completa para PSPACE. Por lo tanto, a menos que haya un avance muy improbable, debe convertir el autómata en uno determinista (esto lleva mucho tiempo) y luego realizar las comprobaciones.
• Puede transformar un FSM no determinista en uno determinista con un número exponencial de estados. Esto es inevitable. Ejercicio (¡no es difícil!): El lenguaje que consiste en palabras en las que la letra n-th del final es "a" se puede reconocer usando un FSM no determinista con n estados, y no se puede reconocer usando un FSM determinista con menos de 2 ⁿ estados El límite exponencial no se puede romper en el caso general.