Minimisation DFA multilingue

Je suis intéressé par une légère généralisation de DFA. Comme d'habitude, nous avons un ensemble d'états , un alphabet fini , une action définie sur par et l'état initial ; mais au lieu de l'ensemble habituelle terminal, nous prenons une famille de sous - ensembles de . Un DFA multilingue est alors le tuple $Q$ $\Sigma$ $\Sigma^*$ $Q$ $\delta : Q\times\Sigma\rightarrow Q$ $q_0$ $(T_i)_{i\in 1..n}$ $Q$ $M$

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

et est reconnu par ssi pour certains . Définissez comme la famille de langues reconnue par M, si vous le souhaitez. $L \subseteq \Sigma^*$ $M$ $L = \{s\in\Sigma^*|q_0s\in T_i\}$ $i\in 1..n$ $(L_i(M))_{i\in 1..n}$

Bon, maintenant pour ma question: étant donné une famille de langues régulières , je veux trouver le DFA tel que décrit ci-dessus de telle sorte que pour tout , c'est-à-dire tel queest minimisé sur toutes ces machines. Ma question est la suivante: existe-t-il des moyens efficaces connus de le faire, peut-être analogues à la théorie de minimisation DFA standard? À l'inverse, existe-t-il des preuves que ce problème pourrait être difficile? $(L_i)_{i\in 1..n}$ $M$ $L_i = L_i(M)$ $i\in 1..n$ $|Q|$

automata-theory dfa gdmclellan
la source

Il me semble que l'algorithme basé sur le raffinement de partition standard, modifié uniquement pour commencer par partitionner l'ensemble initial d'états selon qu'ils acceptent / refusent pour chacun des sous-ensembles donnés plutôt que pour un seul ensemble , devrait simplement fonctionner immédiatement. Pourquoi pas? Il ne divise les paires d'états que lorsqu'elles doivent être divisées, de sorte qu'il génère toujours le raffinement le plus grossier possible des états.

T_{i}

$T_i$

T

$T$

David Eppstein

La preuve du commentaire par @DavidEppstein est facile si vous définissez la relation d'équivalence ssi pour chaque , où est la relation d'équivalence Myhill-Nerode. Vous pouvez ensuite procéder dans le même sens que l'algorithme de minimisation standard.

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

ne comprends pas très bien. est la réponse à ce problème pour trouver le DFA minimal d'une union de DFA avec la même "configuration" sauf des états finaux différents, chaque DFA pour ? aussi le defn de reconnaissance de ne semble pas avoir de sens exactement, il semble mélanger les chaînes et les jeux d'états.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

vzn

Les arguments avancés par DavidEppstein et Shaull semblent convaincants, je trouverai un peu de temps pour passer en revue le théorème de Myhill-Nerode quand j'aurai le temps de me convaincre que le quotient donne toujours l'automate minimal. Avec le recul, cela semble trop évident.

gdmclellan

@vzn: ne veut certainement pas unir les langues de l'automate d'origine; et le peut se chevaucher. Un DFA en plusieurs langues avec les langues et devrait être en mesure de signaler, par exemple, que , mais . Quant à la notation utilisée pour définir la reconnaissance d'une langue, la notation est définie en étendant à une action sur par les règles suivantes pour tous les : .

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

Réponses:

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

Détails . Le cas correspond à la construction standard et le cas général n'est pas très différent dans son esprit. Étant donné une langue et un mot , soit . Définissez une relation d'équivalence sur en définissant Puisque les sont réguliers, cette congruence a un indice fini. De plus, il est facile de voir que chaque est saturé par et que pour chaque , implique $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$ . Notons par le mot vide et par la classe d'un mot . Soit le multi-automate déterministe défini comme suit:

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\}$ .

Par construction, si et seulement si et donc accepte la famille . Reste à prouver que est minimal. Il est en fait minimal au sens algébrique fort (ce qui implique qu'il a le nombre minimal d'états). Soit et soit deux multi-automates. Un morphisme est une carte surjective de sur telle 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'_-$ ,
pour , , $1 \leqslant i \leqslant n$ $f^{-1}(F'_i) = F_i$
pour tout et , . $u \in A^*$ $q \in Q$ $f(q \cdot u) = f(q) \cdot u$

Ensuite, pour tout multi-automate déterministe accessible acceptant , il y a un morphisme de sur . Pour le prouver, on vérifie d'abord que si , alors . Maintenant est défini par où est n'importe quel mot tel que . On peut alors montrer que satisfait les trois propriétés requises. $\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$

La fin est un peu sommaire, faites-moi savoir si vous avez besoin de plus de détails.

J.-E. Épingle
la source