Comment convertir des automates finis en expressions régulières?
On février 16, 2021 by adminLa conversion dexpressions régulières en NFA (minimal) qui acceptent le même langage est facile avec des algorithmes standard, par exemple Lalgorithme de Thompson . Lautre direction semble cependant plus fastidieuse et parfois les expressions qui en résultent sont compliquées.
Quels sont les algorithmes là pour convertir NFA en expressions régulières équivalentes? Y a-t-il des avantages concernant la complexité temporelle ou la taille des résultats?
Ceci est censé être une question de référence. Veuillez inclure une description générale de votre méthode ainsi quune exemple non trivial.
Commentaires
- Notez une question similaire à ladresse cstheory.SE , ce qui nest probablement pas adapté à notre public.
- toutes les réponses utilisent une technique formelle pour écrire lER à partir de DFA. Je pense que ma technique danalyse est relativement simple et objective, je le démontre dans ma réponse. : Quel est le langage de ces automates finis déterministes? Je pense que ce serait utile parfois. Oui, bien sûr, parfois jutilise moi-même une méthode formelle (théorème dArden) écrire RE est La question est complexe comme celle donnée dans cet exemple: Comment écrire une expression régulière pour un DFA
Réponse
Il existe plusieurs méthodes pour effectuer la conversion dautomates finis en expressions régulières. Je décrirai ici celui habituellement enseigné à lécole qui est très visuel. Je pense que cest le plus utilisé dans la pratique. Cependant, écrire lalgorithme nest pas une si bonne idée.
Méthode de suppression détat
Cet algorithme consiste à manipuler le graphe de lautomate et nest donc pas très adapté aux algorithmes car il en a besoin graph primitives telles que … suppression détat. Je vais le décrire en utilisant des primitives de plus haut niveau.
Lidée clé
Lidée est de considérer les expressions régulières sur les arêtes puis de supprimer les états intermédiaires tout en gardant les étiquettes darêtes cohérentes.
Le motif principal peut être vu dans les figures suivantes. Le premier a des étiquettes entre $ p, q, r $ qui sont des expressions régulières $ e, f, g, h, i $ et nous voulons supprimer $ q $.
Une fois enlevé, on compose $ e, f, g, h, i $ ensemble (tout en préservant les autres arêtes entre $ p $ et $ r $ mais cela ne saffiche pas à ce sujet):
Exemple
En utilisant le même exemple que dans Réponse de Raphael :
on supprime successivement $ q_2 $:
puis $ q_3 $:
alors il faut encore appliquer une étoile sur lexpression de $ q_1 $ à $ q_1 $. Dans ce cas, létat final est aussi initial donc nous avons vraiment juste besoin dajouter une étoile:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Lalgorithme
L[i,j]
est lexpression rationnelle du langage de $ q_i $ à $ q_j $. Premièrement, nous supprimons tout mul ti-bords:
for i = 1 to n: for j = 1 to n: if i == j then: L[i,j] := ε else: L[i,j] := ∅ for a in Σ: if trans(i, a, j): L[i,j] := L[i,j] + a
Maintenant, la suppression de létat. Supposons que nous voulions supprimer létat $ q_k $:
remove(k): for i = 1 to n: for j = 1 to n: L[i,i] += L[i,k] . star(L[k,k]) . L[k,i] L[j,j] += L[j,k] . star(L[k,k]) . L[k,j] L[i,j] += L[i,k] . star(L[k,k]) . L[k,j] L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]
Notez quà la fois avec un crayon de papier et avec un algorithme, vous devez simplifier les expressions comme star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(Par main vous nécrivez simplement pas le bord quand ce nest pas $ ∅ $, ou même $ ε $ pour une boucle auto et vous ignorez quand il ny a pas de transition entre $ q_i $ et $ q_k $ ou $ q_j $ et $ q_k $)
Maintenant, comment utiliser remove(k)
? Vous ne devez pas supprimer les états finaux ou initiaux à la légère, sinon vous manquerez des parties du langage.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Si vous navez quun seul état final $ q_f $ et un état initial $ q_s $ alors lexpression finale est:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Si vous avez plusieurs états finaux (ou même des états initiaux), il ny a pas de moyen simple de fusionner ceux-ci, autre que lapplication de la méthode de fermeture transitive Ce nest généralement pas un problème à la main, mais cela est gênant lors de lécriture de lalgorithme. Une solution de contournement beaucoup plus simple consiste à énumérer toutes les paires $ (s, f) $ et à exécuter lalgorithme sur le graphe (déjà supprimé) pour obtenir toutes les expressions $ e_ {s, f} $ en supposant que $ s $ est le seul état initial et $ f $ est le seul état final, puis faire lunion de tous les $ e_ {s, f} $.
Ceci, et le fait que cela modifie les langues plus dynamiquement que la première méthode le fait plus sujet aux erreurs lors de la programmation. Je suggère dutiliser toute autre méthode.
Inconvénients
Il y a beaucoup de cas dans cet algorithme, par exemple pour choisir le nœud à supprimer, le nombre détats finaux à la fin , le fait quun état final peut aussi être initial etc.
Notez que maintenant que lalgorithme est écrit, cela ressemble beaucoup à la méthode de fermeture transitive.Seul le contexte de lusage est différent. Je ne recommande pas dimplémenter lalgorithme, mais utiliser la méthode pour le faire à la main est une bonne idée.
Commentaires
- Dans lexemple, 2ème image, après suppression du nœud » 2 « , il y a un bord manquant – bord de boucle (ab) dans le nœud A.
- @Kabamaru: corrigé. Mais maintenant, je pense que $ \ varepsilon $ dans la 3ème image devrait également être
ab
, et de même peut-être dans lexpression régulière finale. - Vous pouvez faire lalgorithme travailler pour nimporte quel nombre détats initiaux et finaux en ajoutant un nouvel état initial $ q ^ + $ et un nouvel état final $ q ^ – $, et en les connectant aux états initial et final dorigine par $ \ varepsilon $ -edges. Supprimez maintenant tous les états dorigine. Lexpression est alors trouvée sur le seul bord restant de $ q ^ + $ à $ q _- $. La construction ne donnera pas de boucles à $ q ^ + $ ou $ q _- $ car ces états nont pas de resp entrants. bords sortants. Ou si vous êtes strict, ils auront des étiquettes représentant lensemble vide.
- Il y a toujours un problème avec le deuxième exemple: avant la simplification les automates acceptent » ba « , (1, 3, 1) mais après simplification, cela ne ‘ t.
Réponse
Méthode
La plus belle méthode que jai vue est celle qui exprime lautomate comme système déquation des langages (réguliers) qui peuvent être résolu. Cest particulièrement agréable car il semble donner des expressions plus concises que les autres méthodes.
Soit $ A = (Q, \ Sigma, \ delta, q_0, F) $ un NFA sans $ \ varepsilon $ – transitions. Pour chaque état $ q_i $, créez léquation
$ \ qquad \ displaystyle Q_i = \ bigcup \ limits_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ begin {cases} \ {\ varepsilon \} &, \ q_i \ in F \\ \ emptyset &, \ text {else} \ end {cases} $
où $ F $ est lensemble des états finaux et $ q_i \ overset {a} {\ to} q_j $ signifie quil y a une transition de $ q_i $ à $ q_j $ étiquetée avec $ a $ . Si vous lisez $ \ cup $ comme $ + $ ou $ \ mid $ (selon la définition de votre expression régulière), vous voyez quil sagit dune équation dexpressions régulières.
Pour résoudre le système, vous avez besoin dassociativité et distributivité de $ \ cup $ et $ \ cdot $ (concaténation de chaînes), commutativité de $ \ cup $ et Lemme dArden « ¹:
Soit $ L, U, V \ subseteq \ Sigma ^ * $ des langues régulières avec $ \ varepsilon \ notin U $. Ensuite,
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
La solution est un ensemble dexpressions régulières $ Q_i $, un pour chaque état $ q_i $. $ Q_i $ décrit exactement les mots qui peuvent être acceptés par $ A $ lorsquil est démarré dans $ q_i $; donc $ Q_0 $ (si $ q_0 $ est létat initial) est le expression souhaitée.
Exemple
Pour plus de clarté, nous désignons les ensembles de singleton par leur élément, cest-à-dire $ a = \ {a \} $. lexemple est dû à Georg Zetzsche.
Considérons t son NFA:
[ source ]
Le système déquation correspondant est:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ cup \ varepsilon \\ Q_1 & = bQ_0 \ cup aQ_2 \\ Q_2 & = aQ_0 \ cup bQ_1 \ end {align} $
Maintenant, branchez la troisième équation dans la deuxième:
$ \ qquad \ begin {align} Q_1 & = bQ_0 \ cup a (aQ_0 \ cup bQ_1) \\ & = abQ_1 \ cup (b \ cup aa) Q_0 \\ & = (ab) ^ * ( b \ cup aa) Q_0 \ end {align} $
Pour la dernière étape, nous appliquons le lemme dArden avec $ L = Q_1 $, $ U = ab $ et $ V = (b \ cup aa) \ cdot Q_0 $. Notez que les trois langues sont régulières et $ \ varepsilon \ notin U = \ {ab \} $, ce qui nous permet dappliquer le lemme. Maintenant, nous connectons ce résultat à la première équation:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ cup baQ_0 \ cup bb (ab) ^ * (b \ cup aa) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(par le lemme dArden)} \ end {align} $
Ainsi, nous avons trouvé une expression régulière pour le langage accepté par lautomate ci-dessus, à savoir
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Notez que cest assez succinct (comparer avec le résultat dautres méthodes) mais pas uniquement déterminées; la résolution du système déquations avec une séquence de manipulations différente conduit à dautres expressions – équivalentes! -.
- Pour une preuve dArden » s Lemme, voir ici .
Commentaires
- Quoi est la complexité temporelle de cet algorithme? Y a-t-il une limite sur la taille de lexpression produite?
- @jmite: Je nai aucune idée. Je ne ‘ Je ne pense pas ‘ d’essayer de l’implémenter (d’autres méthodes semblent plus faisables à cet égard) mais je l’utilise comme une méthode stylo-papier.
- Ici ‘ sa mise en œuvre Prolog de cet algorithme: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … mais son prédicat
maybe_union/2
pourrait utiliser plus de travail (en particulier pour éliminer le préfixe commun) pour rendre les expressions régulières plus ordonnées Une autre façon de voir cette méthode est de la comprendre comme une traduction dune expression régulière en grammaire linéaire droite, où les langages avec unification de type Prolog ou correspondance de modèles de type ML constituent de très bons transducteurs, donc ‘ nest pas seulement un algorithme stylo-papier 🙂 - Une seule question Le ε dans la première équation est dû au fait que Qo est un état de départ ou parce que ‘ est un état final? De la même manière si jai deux états finaux sapplique?
- @PAOK Vérifiez la définition de $ Q_i $ ci-dessus (la ligne); il ‘ car $ q_0 $ est un état final.
Réponse
Méthode algébrique de Brzozowski
Cest la même méthode que celle décrite dans la réponse de Raphael , mais à partir dun point de vue dun algorithme systématique, puis, en fait, de lalgorithme. Cela savère facile et naturel à mettre en œuvre une fois que vous savez par où commencer. De plus, cela peut être plus facile à la main si dessiner tous les automates nest pas pratique pour une raison quelconque.
Lorsque vous écrivez un algorithme, vous devez vous rappeler que les équations doivent toujours être linéaires afin davoir une bonne représentation abstraite des équations, chose que vous pouvez oublier lorsque vous résolvez à la main.
Lidée de lalgorithme
Je ne décris pas comment il fonctionne car il est bien fait dans la réponse de Raphael que je Je suggère de lire avant. Au lieu de cela, je me concentre sur l’ordre dans lequel vous devez résoudre les équations sans faire trop de co mputations ou cas supplémentaires.
À partir de la solution ingénieuse de la règle dArden « $ X = A ^ * B $ à léquation du langage $ X = AX∪B $ on peut considérer lautomate comme un ensemble déquations de la forme:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
nous pouvons résoudre cela par récurrence sur $ n $ en mettant à jour les tableaux $ A_ {i, j} $ et $ B_ {i, j} $ en conséquence. A létape $ n $, nous avons:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
et La règle dArden nous donne:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 +… + A_ {n, n-1} X_ {n -1}) $$
et en définissant $ B « _n = A_ {n, n} ^ * B_n $ et $ A » _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ nous obtenons:
$$ X_n = B « _n + A » _ {n, 1} X_1 +… + A « _ {n, n-1} X_ {n -1} $$
et nous pouvons alors supprimer tous les besoins de $ X_n $ dans le système en définissant, pour $ i, j < n $:
$$ B « _i = B_i + A_ {i, n} B » _n $$ $$ A « _ {i, j} = A_ {i, j} + A_ {i, n} A « _ {n, j} $$
Lorsque nous avons résolu $ X_n $ quand $ n = 1 $, nous obtenons une équation comme celle-ci:
$$ X_1 = B » _1 $$
sans $ A « _ {1, i} $. Ainsi nous avons notre expression régulière.
Lalgorithme
Grâce à cela, nous pouvons construire lalgorithme. Pour avoir la même convention que dans linduction ci-dessus, nous dirons que létat initial est $ q_1 $ et que le nombre détats est $ m $. Tout dabord, linitialisation pour remplir $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
et $ A $:
for i = 1 to m: for j = 1 to m: for a in Σ: if trans(i, a, j): A[i,j] := a else: A[i,j] := ∅
puis la résolution:
for n = m decreasing to 1: B[n] := star(A[n,n]) . B[n] for j = 1 to n: A[n,j] := star(A[n,n]) . A[n,j]; for i = 1 to n: B[i] += A[i,n] . B[n] for j = 1 to n: A[i,j] += A[i,n] . A[n,j]
lexpression finale est alors:
e := B[1]
Implémentation
Même si cela peut sembler un système déquations qui semble trop symbolique pour un algorithme, celui-ci est bien adapté pour une implémentation. Voici une implémentation de cet algorithme en Ocaml (lien rompu) . Notez quà part la fonction brzozowski
, tout est à imprimer ou à utiliser pour lexemple de Raphaël. Notez quil existe une fonction étonnamment efficace de simplification des expressions régulières simple_re
.
Commentaires
- Le lien est mort …
- Implémentation en Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Merci pour cette excellente explication. Si je comprends bien, votre pseudo-code dinitialisation suppose que pour i et j donnés, il y a au plus un a tel que (i, a, j) soit une transition. Ceci est correct si nous acceptons détiqueter cette transition avec lexpression rationnelle qui correspond à toutes les lettres de Σ cette étiquette transite de i à j dans lautomate de lettre, mais alors votre notation a dans Σ est un peu étrange car ce nest pas vraiment une lettre. Si nous allons lettre par lettre, nous pouvons avoir plusieurs transitions de i à j et faire lunion de leurs étiquettes dans le corps de la boucle.
Réponse
Méthode de fermeture transitive
Cette méthode est facile à écrire dans un formulaire dun algorithme, mais génère des expressions régulières absurdement grandes et nest pas pratique si vous le faites à la main, principalement parce que cest trop systématique. Cest une bonne et simple solution pour un algorithme.
Lidée clé
Soit $ R ^ k_ {i, j} $ lexpression régulière pour les chaînes allant de $ q_i $ à $ q_j $ en utilisant les états $ \ {q_1,…, q_k \} $. Soit $ n $ le nombre détats de lautomate.
Supposons que vous connaissiez déjà lexpression régulière $ R_ {i, j} $ de $ q_i $ à $ q_j $ sans létat intermédiaire $ q_k $ (sauf pour les extrémités), pour tout $ i, j $. Ensuite, vous pouvez deviner comment lajout dun autre état affectera la nouvelle expression régulière $ R « _ {i, j} $: cela ne change que si vous avez des transitions directes vers $ q_k $, et cela peut être exprimé comme ça:
$$ R « _ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ est $ R ^ {k-1} $ et $ R « $ est $ R ^ k $.)
Exemple
Nous utiliserons le même exemple que dans la réponse de Raphael . Au début, vous ne pouvez utiliser que les transitions directes.
Voici la première étape (notez quune boucle self avec un label $ a $ aurait transformé le premier $ ε $ en $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
À la deuxième étape, nous pouvons utiliser $ q_0 $ (qui est renommé en $ q_1 $ pour nous, car $ R ^ 0 $ est déjà utilisé pour ci-dessus). Nous verrons comment fonctionne $ R ^ 1 $.
De $ q_2 $ à $ q_2 $: $ R ^ 1_ {2,2} = R ^ 0_ {2,2} + R ^ 0_ {2,1} {R ^ 0_ {1,1}} ^ * R ^ 0_ {1,2} = ε + b ε ^ * a = ε + ba $.
Cest parce que passer de $ q_2 $ à $ q_2 $ en utilisant seulement $ q_1 $ comme état intermédiaire peut être fait en restant ici ($ ε $) ou en allant à $ q_1 $ ($ a $), en boucle là-bas ($ ε ^ * $) et revenir ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Vous pouvez calculer comme ça $ R ^ 2 $ et $ R ^ 3 $, aussi, et $ R ^ 3_ {1,1 } $ vous donnera lexpression finale car $ 1 $ est à la fois initial et final. Notez que de nombreuses simplifications dexpressions ont été effectuées ici. Sinon, le premier $ a $ de $ R ^ 0 $ serait $ (∅ + a) $ et le premier $ a $ de $ R ^ 1 $ serait $ ((∅ + a) + ε (ε) ^ * a ) $.
Algorithme
Initialisation:
for i = 1 to n: for j = 1 to n: if i == j: R[i,j,0] := ε else: R[i,j,0] := ∅ for a in Σ: if trans(i, a, j): R[i,j,0] := R[i,j,0] + a
Clôture transitive:
for k = 1 to n: for i = 1 to n: for j = 1 to n: R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)
Alors lexpression finale est (en supposant que $ q_s $ est létat initial):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Mais vous pouvez imaginer il génère des expressions régulières laides. Vous pouvez en effet vous attendre à des choses comme $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $ qui représente le même langage que $ aa $. Notez que simplifier une expression régulière est utile en pratique.
Laisser un commentaire