Un algorithme pour réduire un DFA en introduisant du non-déterminisme?

C'est quelque peu lié à une autre question que j'ai posée , mais je pense qu'elle est suffisamment différente pour justifier sa propre question.

Je fais des recherches où j'essaie de trouver la structure des compléments d'une certaine classe de langages finis. Il est facile pour moi d'obtenir les DFA minimaux acceptant ces langues, mais j'aimerais examiner le type de structure des NFA acceptant ces langages, en particulier comment le non-déterminisme aide à la taille de l'état des automates (les DFA sont exponentiellement grands).

Le problème est que la principale technique de réduction NFA utilise des équivalences, ce qui ne produira aucune réduction si je commence avec un DFA minimal (car il utilise essentiellement la même technique). Si je commence avec un DFA non minimal, il crache simplement le DFA minimal.

Ce que je me demande, est-ce qu'il existe des algorithmes qui peuvent commencer avec un DFA et le réduire en un NFA plus petit en introduisant du non-déterminisme? Existe-t-il des "techniques standard" pour ce faire?

J'ai trouvé des réductions de précommande , qui semblent prometteuses mais difficiles à mettre en œuvre. Je suis ouvert à de nombreuses suggestions.

Pour une heuristique efficace, je suggère de consulter la littérature CAO sur le problème de codage d'état (attribution d'identificateurs binaires aux états d'un DFA pour minimiser la quantité de logique pour la fonction de transition d'état.) Devadas et Newton, "Décomposition et factorisation du fini séquentiel machines d'état ", IEEE TCAD , 8 (11): 1206-1217, 1989 souligne qu'il existe une relation étroite entre le codage d'état et la décomposition de la machine d'état.

Si pour un DFA avec $N$ indique que vous attribuez un unique $M$ identifiant d'état de bit pour chaque état ($\lg_2N < M\leq N$), vous avez alors essentiellement décomposé le DFA en un réseau de $M$machines à deux états en interaction. De manière équivalente: vous avez défini un ensemble$S$ avec $M$ et attribué un sous-ensemble unique de $S$à chaque état dans votre DFA d'origine. C'est aussi ce que fait l' algorithme de construction du jeu de puissance Rabin-Scott . Donc, en faisant un codage d'état sur le DFA, nous essayons de désosser l'ensemble à partir duquel l'algorithme de construction du jeu de puissance est parti.

Dans le problème de codage d'état traditionnel, tous les codages sont légaux et il existe une fonction objective (liée à la quantité de logique dans la fonction de transition d'état) que vous essayez de minimiser. Pour générer un NFA, vous devez résoudre une version contrainte du problème entrant où:

un encodage de $M$les identificateurs de bits vers les états DFA représentent un NFA ssi pour chaque symbole de l'alphabet, la fonction de transition pour chaque bit est une simple disjonction de bits. (Aucune conjonction ou négation n'est autorisée.)

Vous pouvez donc énumérer tous les $M$ encodages de bits pour tous $\lg_2N < M\leq N$et vérifiez si chacun satisfait à la contrainte. (Notez que pour$M=N$ l'encodage trivial "one-hot" satisfait toujours les contraintes et vous donne le DFA.) L'énumération est cependant ridiculement grande (le manuel de Di Micheli le donne comme quelque chose comme $\frac{2^M !}{(2^M - N)!M!}$.) La raison pour laquelle je suggère la littérature CAD est qu'il existe des techniques pour effectuer cette recherche implicitement plutôt que d'énumérer (par exemple, en utilisant des BDD, voir Lin, Touati et Newton, "Don't care minimisation of multi-level sequential. réseaux logiques, " Int'l Conf Comp-Aided Dsgn ICCAD-90: 414-417, 1990 .

Exemple

Prenez le DFA suivant, (avec un codage d'état que j'ai dérivé en trichant (j'ai généré le DFA à partir d'un NFA en utilisant Rabin-Scott, et le codage représente les sous-ensembles choisis par Rabin-Scott.))

Si nous appelons les bits dans l'affectation d'état ABCD, alors lorsque le symbole d'entrée est 1, la fonction de transition est A = A, B = A, C = B, D = C. Lorsque le symbole d'entrée est 0, la fonction de transition est A = A, C = B, D = C. Il s'agit d'une fonction de transition purement disjonctive sans conjonction ni négation, donc ce codage d'état nous donne un NFA. Les états dans le NFA correspondent un à un avec les bits du codage, et la fonction de transition est la suivante:

Formulation comme problème de satisfiabilité booléenne

La description informelle ci-dessus conduit directement à un codage comme un problème de satisfiabilité booléenne. Il existe un ensemble de variables qui décrit les transitions dans le NFA, et un ensemble de variables pour le codage d'état DFA qui serait dérivé de Rabin-Scott pour le NFA choisi. Les transitions du DFA spécifique que vous essayez de décomposer sont utilisées pour placer des contraintes sur les transitions NFA.

Supposons que l'on nous donne un DFA avec $N$ états pour une langue avec $S$ symboles, et nous aimerions en tirer un $M$ état NFA, avec $\lg_2N<M\leq N$. Nous utiliserons les variables$y_{sft}$ pour représenter les transitions possibles dans la NFA. $y_{sft}$sera vrai si il y a une transition dans le NFA de l' état NFA$f$ à l' état NFA$t$sur le symbole $s$. Dans l'exemple ci-dessus NFA, l'alphabet est de taille 2 et il y a 4 états NFA, donc il y a$SM^2=32$ $y$ variables et $y_{0AA}, y_{1AA}$, et $y_{1AB}$ sont tous vrais tout en $y_{1DA}$ c'est faux.

Nous utiliserons les variables $x_{dn}$ pour indiquer si l'algorithme Rabin-Scott doit inclure l'état NFA $n$ dans l'ensemble des états étiquetant l'état DFA $d$. Dans l'exemple ci-dessus, nous avons$N=8$ États DFA et $M=4$ NFA déclare donc il y a 32 $x$variables. Dans l'exemple ci-dessus, supposons que l'état le plus bas (celui intitulé "1011") soit l'état$k$, puis $x_{kA}$, $x_{kC}$, et $x_{kD}$ sont vrais tout $x_{kB}$ c'est faux.

Maintenant les contraintes. Tout d'abord, Rabin-Scott doit trouver un codage différent pour chaque état DFA, donc pour les états DFA$i < j$ et tous les états NFA $\{A,B,\cdots, D\}$:

$$(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).$$

Ensuite, il doit être le cas que si Rabin-Scott a trouvé une transition de l'état DFA $i$ à l'état DFA $j$ sur le symbole $s$ puis pour chaque état NFA $k$ inclus dans le codage de $j$ il doit y avoir un état NFA $l$ de l'encodage de l'état DFA $j$ de telle sorte que la NFA d'origine avait une transition de $l$ à $k$. Dans l'exemple ci-dessus, sur le symbole "1" il y a une transition DFA de l'état DFA "1000" à l'état DFA "1100" donc il doit y avoir une transition NFA de l'état NFA A aux états NFA A et B et aucune transition NFA de NFA l'état A à l'état NFA C ou D. Donc, pour chacun des$o(SN^2)$ bords dans le DFA, nous avons les contraintes:

$$\begin{eqnarray*} x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\ x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\ & & \cdots \\ x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}. \end{eqnarray*}$$

Enfin, nous devons gérer le début et accepter les États. L'état de démarrage DFA est codé avec l'union des états de démarrage NFA, il est donc préférable de ne pas coder l'état de démarrage DFA avec l'ensemble vide.$x_0A + x_0B + \cdots + x_0D$. Et enfin, nous avons besoin d'un ensemble de variables$f_n$pour indiquer si chaque état NFA est un état d'acceptation NFA. Il doit être le cas que le codage pour chaque état DFA accepte contient au moins un état NFA accepte et que le codage pour chaque état DFA non accepté ne contient aucun état NFA accepte donc:$x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$ pour DFA accepte les états $i$ et $\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$ pour les États non acceptés par DFA $j$.

La réduction des NFA est difficile, si difficile en effet que même l'approximation est difficile; voir Minimizing NFA's and Regular Expressions par Gramlich et Schnitger (2005). Cet article semble également contenir des références utiles, par exemple les algorithmes de réduction de la NFA au moyen des inégalités régulières de Champarnaud et Coulon (2002) qui contiennent des techniques de minimisation.

Il existe quelques notions de canonique FSA qui ne sont pas nécessairement déterministes et peuvent donc être plus petites que le DFA minimal. Un exemple est les FSA "résiduelles", pour lesquelles on peut calculer des FSA résiduelles canoniques assez directement, voir F. Denis, A. Lemay et A. Terlutte. "Automates à états finis résiduels", Fundamenta Informaticae 51 (4): 339-368, 2002 . Plusieurs alternatives existent.