Minimización de DFA en varios idiomas

Estoy interesado en una ligera generalización de DFA. Como de costumbre, tenemos un conjunto de estados $Q$ , un alfabeto finito $\Sigma$ , una acción $\Sigma^*$ definida en $Q$ por $\delta : Q\times\Sigma\rightarrow Q$ , y un estado inicial $q_0$ ; pero en lugar del conjunto de terminales de costumbre, tomamos una familia $(T_i)_{i\in 1..n}$ de subconjuntos de $Q$ . Un multi-idioma de DFA $M$ es entonces la tupla

$(Q, \Sigma, \delta, q_0, (T_i))$

y $L \subseteq \Sigma^*$ es reconocido por $M$ iff $L = \{s\in\Sigma^*|q_0s\in T_i\}$ para algunos $i\in 1..n$ . Defina $(L_i(M))_{i\in 1..n}$ como la familia de idiomas reconocida por M, si lo desea.

Bien, ahora para mi pregunta: dada una familia de idiomas regulares $(L_i)_{i\in 1..n}$ , quiero encontrar el mínimo DFA varios idiomas $M$ como se describió anteriormente, de modo que $L_i = L_i(M)$ para todos $i\in 1..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?

automata-theory dfa gdmclellan
fuente

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

, 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.

T_{i}

$T_i$

T

$T$

David Eppstein

La prueba del comentario de @DavidEppstein es fácil si define la relación de equivalencia

iff

para cada

, donde

es la relación de equivalencia de Myhill-Nerode. Luego puede seguir las mismas líneas que el algoritmo de minimización estándar.

x \sim y

$x\sim y$

x \sim_{T_{i}} y

$x\sim_{T_i}y$

i

$i$

x \sim_{T_{i}} y

$x\sim_{T_i} y$

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

no parece tener sentido exactamente, parece mezclar cadenas y conjuntos de estados.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

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

debería ser capaz de informar, por ejemplo, que

, pero

. En cuanto a la notación utilizada para definir el reconocimiento de un lenguaje, la notación se define extendiendo

a una acción

mediante las siguientes reglas para todos

T_{i}

$T_i$

A

$A$

B

$B$

s \in A

$s\in A$

s \notin B

$s\notin B$

δ

$\delta$

Σ^{*}

$\Sigma^*$

Q

$Q$

q \in Q, σ \in Σ, s \in Σ^{*}

$q\in Q, \sigma\in\Sigma, s\in\Sigma^*$

q σ = δ (q, σ), q (s σ) = (q s) σ

$q\sigma = \delta(q, \sigma), q(s\sigma) = (qs)\sigma$

gdmclellan

Respuestas:

$\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$

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 , implica $n = 1$ $L$ $u$ $u^{-1}L = \{ v \in A^* \mid uv \in L \}$ $\sim$ $A^*$

u \sim v ⟺ for each L \in L, u^{- 1} L = v^{- 1} L

$u \sim v \iff \text{for each }L \in \mathcal{L},\ u^{-1}L = v^{-1}L$

L_{i}

$L_i$

L_{i}

$L_i$

\sim

$\sim$

a \in A

$a \in A$

u \sim v

$u \sim v$

u a \sim v a

$ua \sim va$ . 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

$1$

[u]

$[u]$

\sim

$\sim$

u

$u$

A_{L} = (Q, [1], \cdot, (F_{i})_{1 ⩽ i ⩽ n})

$\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$

$Q = \{ [u] \mid u \in A^*\}$ ,
$[u] \cdot a = [ua]$ ,
$F_i = \{ [u] \mid u \in L_i\}$ .

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] \cdot u \in F_i$ $u \in L_i$ $\mathcal{A}_\mathcal{L}$ $\mathcal{L}$ $\mathcal{A}_\mathcal{L}$ $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ $f: \mathcal{A} \to \mathcal{A}'$ $Q$ $Q'$

$f(q_-) = q'_-$ ,
para , , $1 \leqslant i \leqslant n$ $f^{-1}(F'_i) = F_i$
para todo y , . $u \in A^*$ $q \in Q$ $f(q \cdot u) = f(q) \cdot 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. $\mathcal{A}$ $\mathcal{L}$ $\mathcal{A}$ $\mathcal{A}_\mathcal{L}$ $q_- \cdot u_1 = q_- \cdot u_2 = q$ $u_1 \sim u_2$ $f$ $f(q) = [u]$ $u$ $q_- \cdot u = q$ $f$

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

J.-E. Alfiler
fuente