Minimización de DFA en varios idiomas

10

Estoy interesado en una ligera generalización de DFA. Como de costumbre, tenemos un conjunto de estados Q , un alfabeto finito Σ , una acción Σ definida en Q por δ:Q×ΣQ , y un estado inicial q0 ; pero en lugar del conjunto de terminales de costumbre, tomamos una familia (Ti)i1..n de subconjuntos de Q . Un multi-idioma de DFA M es entonces la tupla

(Q,Σ,δ,q0,(Ti))

y LΣ es reconocido por M iff L={sΣ|q0sTi} para algunos i1..n . Defina (Li(M))i1..n como la familia de idiomas reconocida por M, si lo desea.

Bien, ahora para mi pregunta: dada una familia de idiomas regulares (Li)i1..n , quiero encontrar el mínimo DFA varios idiomas Mcomo se describió anteriormente, de modo que Li=Li(M) para todos i1..n , es decir, tal que |Q|se minimiza sobre todas estas máquinas. Mi pregunta es, ¿hay alguna forma eficiente de hacer esto, tal vez análoga a la teoría estándar de minimización de DFA? Por el contrario, ¿hay alguna evidencia de que este problema pueda ser difícil?

gdmclellan
fuente
77
Me parece que el algoritmo estándar basado en el refinamiento de partición, modificado solo para comenzar mediante la partición del conjunto inicial de estados, ya sea que estén aceptando / no aceptando cada uno de los subconjuntos dados lugar de un solo conjunto T , debería trabajar de inmediato ¿Por qué no lo haría? Solo divide pares de estados cuando deben dividirse, por lo que aún genera el refinamiento más grueso posible de los estados. TiT
David Eppstein
1
La prueba del comentario de @DavidEppstein es fácil si define la relación de equivalencia iff x T i y para cada i , donde x T i y es la relación de equivalencia de Myhill-Nerode. Luego puede seguir las mismas líneas que el algoritmo de minimización estándar. xyxTiyixTiy
Shaull
No entiendo del todo. ¿Es la respuesta a este problema encontrar el DFA mínimo de una unión de DFA con la misma "configuración", excepto diferentes estados finales, cada DFA para ? También la definición de reconocimiento de L = { . . . } no parece tener sentido exactamente, parece mezclar cadenas y conjuntos de estados. 1..nL={...}
vzn
Los puntos planteados por David Eppstein y Shaull parecen convincentes. Encontraré algo de tiempo para repasar el teorema de Myhill-Nerode cuando tenga tiempo de convencerme de que el cociente aún produce el mínimo autómata. En retrospectiva, parece demasiado obvio.
gdmclellan
@vzn: definitivamente no quiero unir los idiomas del autómata original; y el puede superponerse. Un multi-idioma de DFA con lenguajes Una y B debería ser capaz de informar, por ejemplo, que s A , pero s B . En cuanto a la notación utilizada para definir el reconocimiento de un lenguaje, la notación se define extendiendo δ a una acción Σ en Q mediante las siguientes reglas para todos q Q , σ Σ , s Σ :TiABsAsBδΣQqQ,σΣ,sΣ . qσ=δ(q,σ),q(sσ)=(qs)σ
gdmclellan

Respuestas:

14

L=(Li)1in

Detalles . El caso corresponde a la construcción estándar y el caso general no es muy diferente en espíritu. Dado un lenguaje y una palabra , dejemos . Defina una relación de equivalencia en estableciendo Since los son regulares, esta congruencia tiene un índice finito. Además, es fácil ver que cada está saturado por y que para cada , implicaL u u - 1 L = { v A u v L } A u vn=1Luu1L={vAuvL}AL i L ia A u v u a v a 1 [ u ] u A L = ( Q , [ 1 ] , , ( F i ) 1 i n )

uvfor each LL, u1L=v1L
LiLiaAuvuava. Denotemos por la palabra vacía y por la clase de una palabra . Sea sea ​​el multi-autómata determinista definido de la siguiente manera:1[u]uAL=(Q,[1],,(Fi)1in)
  1. Q={[u]uA} ,
  2. [u]a=[ua] ,
  3. Fi={[u]uLi} .

Por construcción, si y solo si y, por lo tanto, acepta la familia . Queda por demostrar que es mínimo. En realidad, es mínimo en un sentido algebraico fuerte (lo que implica que tiene el número mínimo de estados). Sea y ser dos multi-autómatas. Un morfismo es un mapa dejetivo de a tal que[1]uFiuLiALLALA=(Q,q,,(Fi)1in)A=(Q,q,,(Fi)1in)f:AAQQ

  1. f(q)=q ,
  2. para , , 1inf1(Fi)=Fi
  3. para todo y , .uAqQf(qu)=f(q)u

Entonces, para cualquier multi-autómata determinista accesible acepte , hay un morfismo de a . Para probar esto, primero se verifica que si , entonces . Ahora se define por donde es cualquier palabra tal que . Entonces se puede demostrar que satisface las tres propiedades requeridas.L A A L q -u 1 = q -u 2 = q u 1u 2 f f ( q ) = [ u ] u q -u = q fALAALqu1=qu2=qu1u2ff(q)=[u]uqu=qf

El final es un poco incompleto, avíseme si necesita más detalles.

J.-E. Alfiler
fuente