Algoritmos para minimizar los autómatas de Moore

10

El algoritmo de Brzozowski se puede extender a los autómatas de Moore, pero su complejidad temporal es exponencial en general. ¿Hay algún otro algoritmo para minimizar los autómatas de Moore? ¿Cuáles son los tiempos de ejecución de estos algoritmos si los hay?

Ajeet Singh
fuente
¿A qué algoritmo de Brzozowski te refieres? ¿El que usa derivadas de expresiones regulares?
J.-E.
2
Bienvenido a SE Computer Science. Como aparentemente aún no leyó la presentación del sitio, debe saber que es un trabajo cooperativo, basado en el intercambio técnico entre usuarios que hacen preguntas y usuarios que brindan respuestas o comentarios. Por lo tanto, se considera apropiado responder a los usuarios que solicitan más detalles en los comentarios, votar a favor de buenas respuestas o buenos comentarios (u otras preguntas o respuestas interesantes que leas) y, en última instancia, aceptar la respuesta que consideres mejor para tus preguntas haciendo clic en " marque el signo "(como una V) de la izquierda de la respuesta elegida.
babou
¿Te sirvió la respuesta?
babou

Respuestas:

6

El algoritmo de minimización DFA original fue diseñado para máquinas Moore , guiado por su comportamiento aparentemente más observable. Pero el algoritmo presentado aquí es una reconstrucción de la minimización de DFA, ya que descubrí la evidencia histórica después del hecho.

Después de Wikipedia (con algunos cambios notacionales):

Una máquina Moore se puede definir como una tupla de 6 consiste en lo siguiente:(Q,q0,Σ,Π,δ,γ)

  • un conjunto finito de estados Q
  • un estado inicial (también llamado estado inicial) que es un elemento de Qq0Q
  • un conjunto finito llamado alfabeto de entrada Σ
  • un conjunto finito llamado alfabeto de salida Λ
  • una función de transición mapeando un estado y el alfabeto de entrada al siguiente estado δ:Q×ΣQ
  • una función de salida mapeando cada estado al alfabeto de salida γ:QΠ

A partir de esta definición, una máquina Moore es un transductor determinista de estado finito.

No tengo referencia para la minimización de los autómatas de Moore. Sin embargo, no parece demasiado difícil imaginar un algoritmo, derivado del algoritmo utilizado para autómatas deterministas de estado finito.

La idea en la minimización de DFA se basa en la caracterización de Myhill-Nerode de los idiomas regulares .

LxyzxzyzLRLxRLyxyRL

LRLLRL

qWqRL

LWqRL

Por lo tanto, la minimización del DFA en realidad consiste en fusionar estados (considerados como conjuntos de cadenas equivalentes), siempre que se demuestre que dos estados distintos contienen cadenas equivalentes.

O(n2)O(nlogn)

RTTRLRT

TxyzT(xz)=T(x)uT(yz)=T(y)vuvzxy

RTΣ

El siguiente algoritmo imita el algoritmo de Moore para la minimización de DFA.

PQSe

eΠ:Se={qQγ(q)=e}

P

S
   aΣ,
     SP,qS,δ(q,a)S
     SSi
      SiSPqSi,δ(q,a)S
      SiSP

Cuando no quede ninguna clase que deba dividirse, las clases restantes de estados formarán los estados de la máquina mínima de Moore.

Por construcción, todos los estados en una clase tienen la misma salida que es la salida para la clase.

aΣ

n=|Q|s=|Σ|
nO(sn2)

No tengo ninguna referencia para esta minimización de las máquinas Moore. Posiblemente está incluido en su artículo:

Moore, Edward F (1956). "Experimentos Gedanken en máquinas secuenciales". Automata Studies , Annals of Mathematical Studies (Princeton, NJ: Princeton University Press) (34): 129-153.

Este documento es la referencia principal que presenta las Máquinas Moore . También es la referencia para el algoritmo de minimización DFA de Moore . Por lo tanto, debería ser sorprendente si la adaptación del algoritmo a la minimización de las máquinas Moore no se sugiriera al menos en ese documento. Verifiqué el documento, y la versión del algoritmo de minimización que se presenta es en realidad para máquinas Moore, no para DFA. El documento está bien escrito, pero el estilo de la época hace que sea un poco más difícil de leer. Es interesante ver que muchas de las ideas de la teoría de Myhill-Nerode de las máquinas de estados finitos ya están esbozadas en este documento.

O(snlogn)

babou
fuente
@Raphael Una referencia ... Bueno, tienes suerte, rediseñé el algoritmo porque no tengo acceso a una biblioteca. Pero ya que pediste una referencia, te conseguí una. Te gustaria Pero no estoy seguro de usarlo para enseñar.
babou
@Raphael El artículo es interesante en su presentación que intenta ser muy intuitivo, más operativo que algebraico. No recuerdo todos los detalles de la contribución de Myhill y Nerode (dos años después, en 1958), y no leí el documento con suficiente atención (más bien lo hojeé), pero me pregunto si la teoría no debería atribuirse a Moore como bien.
babou
2

Una versión del algoritmo de Brzozowski usando derivadas de expresiones regulares se da en [2], Capítulo 12, Sección 4, donde se acredita a [4]. Ver [1] y [3] para el caso más general de transductores subsecuentes (la terminología está un poco desactualizada y el término transductor secuencial es probablemente más apropiado hoy en día).

[1] C. Choffrut, Minimizando transductores subsecuenciales: una encuesta, Theoret. Comp. Sci. 292 (2003), 131–143.

[2] S. Eilenberg, Autómatas, Idiomas y máquinas, vol. A, Academic Press, 1974.

[3] J.-E. Pin, un tutorial sobre funciones secuenciales . (Diapositivas)

[4] GN Raney, Funciones secuenciales, JACM 5 (1958), 177–180.

J.-E. Alfiler
fuente
@DW Gracias por la edición. Simplemente perfecto.
J.-E.
1

El algoritmo de Brzozowski es un mal punto de partida (si le preocupa el tiempo de ejecución asintótico del peor de los casos). Incluso Wikipedia te dice lo mismo:

Como observó Brzozowski (1963), invertir los bordes de un DFA produce un autómata finito no determinista (NFA) para la inversión del lenguaje original, y convertir este NFA en un DFA utilizando la construcción de conjunto de potencia estándar (construyendo solo los estados accesibles de el DFA convertido) conduce a un DFA mínimo para el mismo idioma invertido. La repetición de esta operación de inversión por segunda vez produce un DFA mínimo para el idioma original. La complejidad del peor de los casos del algoritmo de Brzozowski es exponencial, ya que existen lenguajes regulares para los cuales el DFA mínimo de la inversión es exponencialmente mayor que el DFA mínimo del lenguaje, [6] pero con frecuencia funciona mejor de lo que sugeriría este peor caso.

El algoritmo tiene un tiempo de ejecución exponencial en el peor de los casos, incluso en DFA porque calcula un autómata para el reverso, que puede ser exponencialmente grande. Por lo tanto, su problema no proviene de la extensión a los transductores.

Intente adaptar otro algoritmo de minimización de DFA.

Rafael
fuente