Algorithmes pour minimiser les automates de Moore

L'algorithme de Brzozowski peut être étendu aux automates de Moore mais sa complexité temporelle est exponentielle en général. Existe-t-il un autre algorithme pour minimiser les automates Moore? Quels sont les temps d'exécution de ces algorithmes, le cas échéant?

L'algorithme de minimisation DFA d'origine a été conçu pour Moore Machines , guidé par leur comportement apparemment plus observable. Mais l'algorithme présenté ici est une reconstruction à partir de la minimisation DFA, puisque j'ai découvert les preuves historiques après coup.

Après Wikipedia (avec quelques changements de notation):

Une machine Moore peut être définie comme un 6-tuple composé des éléments suivants:$(Q, q_0, \Sigma, \Pi, \delta, \gamma)$

• un ensemble fini d'états $Q$
• un état de départ (également appelé état initial) qui est un élément de $q_0$$Q$
• un ensemble fini appelé l'alphabet d'entrée $\Sigma$
• un ensemble fini appelé l'alphabet de sortie $\Lambda$
• une fonction de transition mappant un état et l'alphabet d'entrée à l'état suivant $\delta : Q \times \Sigma \rightarrow Q$
• une fonction de sortie mappant chaque état à l'alphabet de sortie $\gamma : Q \rightarrow \Pi$

D'après cette définition, une machine Moore est un transducteur déterministe à états finis.

Je n'ai aucune référence pour la minimisation des automates Moore. Cependant, il ne semble pas trop difficile d'imaginer un algorithme, dérivé de l'algorithme utilisé pour les automates à états finis déterministes.

L'idée de la minimisation DFA est basée sur la caractérisation Myhill-Nerode des langages réguliers .

Etant donné un langage , et une paire de chaînes x et y , définir une extension de distinction pour être une chaîne z de telle sorte que exactement l' un des deux chaînes x z et y z appartient à L . Définissez une relation R L sur les chaînes par la règle que x R L y ssi il n'y a pas d'extension distinctive pour x et y . Il est facile de montrer que R L est une relation d'équivalence sur les chaînes, et donc il divise l'ensemble de toutes les chaînes en classes d'équivalence.$L$$x$$y$$z$$xz$$yz$$L$$R_L$$x R_L y$$x$$y$$R_L$

Le théorème de Myhill-Nerode déclare que est régulier si et seulement si R L a un nombre fini de classes d'équivalence, et de plus que le nombre d'états dans le plus petit automate fini déterministe (DFA) reconnaissant L est égal au nombre de classes d'équivalence dans R L .$L$$R_L$$L$$R_L$

En effet , chaque état du plus petit DFA est telle que W q tel que défini ci - dessus est l' une des classes d'équivalence pour la relation R L .$q$$W_q$$R_L$

Pour un DFA non minimal pour la langue régulière , il est facile de montrer que chaque jeu W q contient des chaînes qui appartiennent tous à une même classe équivalente par rapport à R L .$L$$W_q$$R_L$

Par conséquent, la minimisation du DFA consiste en fait à fusionner des états (considérés comme des ensembles de chaînes équivalentes), chaque fois qu'il est démontré que deux états distincts contiennent des chaînes équivalentes.

Il existe à cet effet deux algorithmes assez rapides, l'algorithme de Moore (1956) qui est au temps et l'algorithme de Hopcroft (1971) au temps O ( n log n ) .$O(n^2)$$O(n\log n)$

L'extension de Moore automates est mieux compris dans la redéfinition de la relation d'équivalence en tant que pour un transducteur T . La relation R L s'inquiétait de savoir si une contribution future conduirait de manière équivalente à un état acceptant. La relation d'équivalence R T des automates de Moore cherche à savoir si les entrées futures produiront la même sortie.$R_T$$T$$R_L$$R_T$

Par conséquent, étant donné un transducteur , et deux chaînes x et y , nous définissons une extension distinctive comme étant une chaîne z telle que T ( x z ) = T ( x ) u et T ( y z ) = T ( y ) v avec u ≠ v , c'est-à-dire tel que le comportement de sortie du transducteur diffère pour z selon qu'il suit x ou y .$T$$x$$y$$z$$T(xz)=T(x)u$$T(yz)=T(y)v$$u\neq v$$z$$x$$y$

Encore une fois, est une relation d'équivalence, divisant toutes les chaînes de Σ ∗ en classes d'équivalence. Dans le cas d'une machine Moore, ces classes correspondront à nouveau à l'état du transducteur minimal.$R_T$$\Sigma^*$

L'algorithme suivant imite l'algorithme de Moore pour la minimisation DFA.

Nous définissons une partition initiale de Q en classes d'états S e comme suit:$\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Ensuite, nous avons divisé les classes en comme suit:$\mathcal P$

répéter successivement pour chaque classe d'états , jusqu'à ce qu'aucun changement ne se répète ∀ a ∈ Σ $S$
$\ \ $ $\forall a\in\Sigma,\;$
$\ \ \ \ $ Si alorsne riendiviser d'autre S en sous-ensembles S i de telle sorte quepour chaque sous-ensemble S i , il existe une classe différente S ′ ∈ P telle que ∀ q ∈ S i$\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$$S'\in \mathcal P$ (les sous-ensembles S i remplacent S dans P )$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $$S_i$$S$$\mathcal P$

Lorsqu'il ne reste aucune classe à diviser, les classes d'états restantes formeront les états de la machine Moore minimale.

Par construction, tous les états d'une classe ont la même sortie qui est la sortie de la classe.

De même, pour toute entrée , tous les états d'une classe passent à un état de la même autre classe, qui définit la fonction de transition pour la machine minimale de Moore.$a\in\Sigma$

$n=|Q|$$s=|\Sigma|$
$n$$O(sn^2)$

Je n'ai aucune référence pour cette minimisation des machines Moore. Il est peut-être inclus dans son article:

Moore, Edward F (1956). "Expériences de Gedanken sur des Machines Séquentielles". Automata Studies , Annals of Mathematical Studies (Princeton, NJ: Princeton University Press) (34): 129-153.

Ce document est la principale référence introduisant Moore Machines . C'est également la référence de l'algorithme de minimisation DFA de Moore . Il serait donc surprenant que l'adaptation de l'algorithme à la minimisation des machines Moore n'ait pas au moins été suggérée dans cet article. J'ai vérifié le papier et la version de l'algorithme de minimisation présentée est en fait pour les machines Moore, pas pour DFA. Le papier est bien écrit, mais le style de l'époque le rend un peu plus difficile à lire. Il est intéressant de voir que de nombreuses idées de la théorie de Myhill-Nerode des machines à états finis sont déjà esquissées dans cet article.

$O(sn\log n)$

Une version de l'algorithme de Brzozowski utilisant des dérivées d'expressions régulières est donnée dans [2], chapitre 12, section 4, où il est crédité à [4]. Voir [1] et [3] pour le cas plus général des transducteurs sous- séquentiels (la terminologie est un peu dépassée et le terme transducteur séquentiel est probablement plus approprié de nos jours).

[1] C. Choffrut, Minimiser les transducteurs sous-séquentiels: une étude, Theoret. Comp. Sci. 292 (2003), 131-143.

[2] S. Eilenberg, Automates, langages et machines, vol. A, Academic Press, 1974.

[3] J.-E. Pin, Un tutoriel sur les fonctions séquentielles . (Diapositives)

[4] GN Raney, Fonctions séquentielles, JACM 5 (1958), 177-180.

L'algorithme de Brzozowski est un mauvais point de départ (si vous êtes concerné par le pire cas d'exécution asymptotique). Même Wikipédia vous en dit autant:

Comme Brzozowski (1963) l'a observé, l'inversion des bords d'un DFA produit un automate fini non déterministe (NFA) pour l'inversion de la langue d'origine, et la conversion de ce NFA en DFA en utilisant la construction standard du jeu de pouvoirs (en ne construisant que les états accessibles de le DFA converti) conduit à un DFA minimal pour la même langue inversée. La répétition de cette opération d'annulation une deuxième fois produit un DFA minimal pour la langue d'origine. La complexité la plus défavorable de l'algorithme de Brzozowski est exponentielle, car il existe des langages réguliers pour lesquels le DFA minimal de l'inversion est exponentiellement plus grand que le DFA minimal du langage, [6] mais il fonctionne souvent mieux que ce que le pire des cas suggère.

L'algorithme a un temps d'exécution exponentiel dans le pire des cas, même sur DFA car il calcule un automate pour l'inverse, qui peut être exponentiellement volumineux. Votre problème ne vient donc pas de l'extension aux transducteurs.

Essayez d'adapter un autre algorithme de minimisation DFA.