Comment convertir des automates finis en expressions régulières?

115

Convertir des expressions régulières en NFA (minimales) acceptant le même langage est facile avec des algorithmes standard, tels que celui de Thompson . L’autre direction semble être plus fastidieuse, cependant, et les expressions résultantes sont parfois désordonnées.

Quels algorithmes existe-t-il pour convertir NFA en expressions régulières équivalentes? Existe-t-il des avantages en termes de complexité temporelle ou de taille des résultats?

Ceci est supposé être une question de référence. Veuillez inclure une description générale de votre méthode ainsi qu'un exemple non trivial.

Raphaël
la source
2
Notez une question similaire sur cstheory.SE qui ne convient probablement pas à notre public.
Raphaël
toutes les réponses utilisent une technique formelle pour écrire des ER de DFA. Je crois que ma technique d'analyse est relativement facile et objective. Je démontre dans ma réponse: Quel est le langage de cet automate fini déterministe? Je pense que ce serait utile parfois. Oui, bien sûr, parfois, j’utilise moi-même une méthode formelle (théorème d’Arden) pour écrire des ER. La question est complexe, comme le montre cet exemple: Comment écrire une expression régulière pour un DFA
Grijesh Chauhan

Réponses:

94

Il existe plusieurs méthodes pour convertir des automates finis en expressions régulières. Je vais décrire ici celui qui est enseigné à l’école et qui est très visuel. Je crois que c'est le plus utilisé dans la pratique. Cependant, l'écriture de l'algorithme n'est pas une si bonne idée.

Méthode de suppression d'état

Cet algorithme concerne le traitement du graphe de l'automate et n'est donc pas très approprié pour les algorithmes car il nécessite des primitives de graphe telles que ... la suppression de l'état. Je vais le décrire en utilisant des primitives de niveau supérieur.

L'idée clé

L'idée est de prendre en compte les expressions régulières sur les bords, puis de supprimer les états intermédiaires tout en préservant la cohérence des étiquettes.

Le schéma principal peut être vu dans les figures suivantes. Le premier a des étiquettes entre qui sont des expressions rationnelles et nous voulons supprimer .e , f , g , h , i qp,q,re,f,g,h,iq

pqr automate

Une fois supprimés, nous composons ensemble (tout en préservant les autres arêtes entre et mais cela ne s’affiche pas):p re,f,g,h,ipr

entrez la description de l'image ici

Exemple

En utilisant le même exemple que dans la réponse de Raphaël :

Automate 1-2-3

on enlève successivement :q2

1-3 automates

et ensuite :q3

1 automate

alors nous devons toujours appliquer une étoile sur l'expression de à . Dans ce cas, l’état final est également initial, il suffit donc d’ajouter une étoile:q 1q1q1

(ab+(b+aa)(ba)(a+bb))

Algorithme

L[i,j]est l'expression rationnelle de la langue de à . Tout d'abord, nous supprimons tous les multi-bords:q jqiqj

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 :qk

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 que les deux avec un crayon de papier et avec un algorithme vous devez simplifier les expressions comme star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅(à la main que vous écrivez ne tout simplement pas le bord quand il ne , ou même pour une auto-boucle et vous ignorez quand il y a pas de transition entre et ou et )εqiqkqjqk

Maintenant, comment utiliser remove(k)? Vous ne devez pas supprimer les états final ou initial à la légère, sinon vous allez perdre des parties de la langue.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Si vous n'avez qu'un seul état final et un seul état initial l'expression finale est la suivante:qfqs

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 n'existe pas de moyen simple de les fusionner, mis à part l'application de la méthode de fermeture transitive. Habituellement, ce n'est pas un problème à la main, mais cela est gênant lors de l'écriture de l'algorithme. Une solution beaucoup plus simple consiste à énumérer toutes les paires et à exécuter l'algorithme sur le graphe (déjà supprimé) pour obtenir toutes les expressions supposant que est le seul état initial et le seul final. état, puis en faisant l'union de tous .(s,f)es,fsfes,f

Ceci et le fait que cela modifie les langages de manière plus dynamique que la première méthode la rendent plus sujette aux erreurs lors de la programmation. Je suggère d'utiliser une autre méthode.

Les inconvénients

Il existe de nombreux cas dans cet algorithme, par exemple pour choisir le nœud à supprimer, le nombre d'états finaux à la fin, le fait qu'un état final peut également être initial, etc.

Notez que maintenant que l’algorithme est écrit, cela ressemble beaucoup à la méthode de fermeture transitive. Seul le contexte de l'utilisation est différent. Je ne recommande pas d'implémenter l'algorithme, mais utiliser la méthode pour le faire à la main est une bonne idée.

jmad
la source
1
Dans l'exemple, 2ème image, après suppression du noeud "2", il manque un bord - le bord de la boucle (ab) du noeud A.
Panos Kal.
@Kabamaru: corrigé. Mais maintenant, je pense que dans la 3ème image devrait également l'être , et peut-être de même dans l'expression régulière finale. εab
Logique errante
Vous pouvez faire fonctionner l'algorithme pour un nombre quelconque d'états initial et final en ajoutant un nouveau initial et un nouvel état final , et en les connectant aux états initial et final d'origine à l'aide de -edges. Maintenant, supprimez tous les états d'origine. L’expression est alors trouvée sur le seul bord restant de à . La construction ne donnera pas de boucles à ou car ces états n'ont pas resp. bords sortants. Ou si vous êtes strict, ils auront des étiquettes représentant l'ensemble vide. q+qεq+qq+q
Hendrik Jan
1
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 la simplification, ce n'est pas le cas.
wvxvw
50

Méthode

La plus belle méthode que j'ai vue est celle qui exprime l'automate comme un système d'équations de langages (normaux) pouvant être résolus. Il est particulièrement intéressant car il semble produire des expressions plus concises que d’autres méthodes.

Soit un NFA sans -transitions. Pour chaque état , créez l'équationA=(Q,Σ,δ,q0,F)εqi

Qi=qiaqjaQj{{ε}, qiF, else

où est l'ensemble des états finaux et signifie qu'il y a une transition de à étiquetée avec . Si vous lisez comme ou (selon votre définition d'expression régulière), vous voyez qu'il s'agit d'une équation d'expressions régulières.Fqiaqjqiqja+

Pour résoudre le système, vous avez besoin d'associativité et de distributivité de et de (concaténation de chaînes), de commutativité de et du lemme d'Arden ¹:

Laissez langues régulières avec . Ensuite,L,U,VΣεU

L=ULVL=UV

La solution est un ensemble d'expressions régulières , une pour chaque état . décrit exactement les mots qui peuvent être acceptés par au démarrage de ; donc (si est l'état initial) est l'expression souhaitée.QiqiQiAqiQ0q0


Exemple

Par souci de clarté, on dénote les ensembles de singleton par leur élément, c'est dire . L'exemple est dû à Georg Zetzsche.a={a}

Considérez cet NFA:

exemple nfa
[ source ]

Le système d'équation correspondant est:

Q0=aQ1bQ2εQ1=bQ0aQ2Q2=aQ0bQ1

Maintenant, branchez la troisième équation dans la seconde:

Q1=bQ0a(aQ0bQ1)=abQ1(baa)Q0=(ab)(baa)Q0

Pour la dernière étape, nous appliquons le lemme d’Arden avec , et . Notez que les trois langues sont normales et , ce qui nous permet d’appliquer le lemme. Maintenant, on branche ce résultat dans la première équation:L=Q1U=abV=(baa)Q0εU={ab}

Q0=a(ab)(baa)Q0baQ0bb(ab)(baa)Q0ε=((abb)(ab)(baa)ba)Q0ε=((abb)(ab)(baa)ba)(by Arden's Lemma)

Ainsi, nous avons trouvé une expression régulière pour le langage accepté par l’automate ci-dessus, à savoir

((a+bb)(ab)(b+aa)+ba).

Notez qu'il est assez succinct (comparez avec le résultat d'autres méthodes) mais n'est pas déterminé de manière unique; résoudre le système d'équation avec une séquence de manipulations différente conduit à un autre - équivalent! -- expressions.


  1. Pour une preuve du lemme d'Arden, voir ici .
Raphaël
la source
1
Quelle est la complexité temporelle de cet algorithme? Y a-t-il une limite à la taille de l'expression produite?
Jmite
@ Jmite: Je n'en ai aucune idée. Je ne pense pas que j'essaierais de mettre cela en œuvre (d'autres méthodes semblent plus réalisables à cet égard), mais je l'utilise comme une méthode au crayon.
Raphaël
1
Voici une implémentation Prolog de cet algorithme: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/… mais son maybe_union/2prédicat pourrait nécessiter plus de travail (notamment en éliminant le préfixe commun) pour créer des expressions régulières plus ordonnées. Une autre façon de voir cette méthode est de la comprendre comme une traduction de regex en grammaire linéaire droite, où les langages avec unification de type Prolog ou la mise en correspondance de motifs de type ML constituent un très bon transducteur, de sorte que ce n'est pas seulement un crayon algorithme :)
wvxvw
Juste une question. Le ε dans la première équation est parce que Qo est un état de départ ou parce que c'est un état final? Même façon si j'ai deux états finaux s'applique?
Georgio3
@PAOK Vérifiez la définition de ci-dessus (la ligne); c'est parce que est un état final. Qiq0
Raphaël
28

Méthode algébrique de Brzozowski

C'est la même méthode que celle décrite dans la réponse de Raphaël , mais du point de vue d'un algorithme systématique, puis de l'algorithme. Il s'avè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 n’est pas pratique pour une raison quelconque.

Lors de l'écriture d'un algorithme, vous devez vous rappeler que les équations doivent toujours être linéaires pour obtenir une bonne représentation abstraite des équations, chose que vous pouvez oublier lorsque vous résolvez à la main.

L'idée de l'algorithme

Je ne décrirai pas comment cela fonctionne car c'est bien fait dans la réponse de Raphaël que je suggère de lire auparavant. Au lieu de cela, je me concentre sur l'ordre dans lequel vous devez résoudre les équations sans faire trop de calculs ou de cas supplémentaires.

En partant de la solution ingénieuse de la règle d’ Arden à l’équation du langage nous pouvons considérer l’automate comme un ensemble d’équations de la forme:X=ABX=AXB

Xi=Bi+Ai,1X1++Ai,nXn

nous pouvons résoudre ce problème par induction sur en mettant à jour les tableaux et conséquence. A l'étape , on a:nAi,jBi,jn

Xn=Bn+An,1X1++An,nXn

et la règle d'Arden nous donne:

Xn=An,n(Bn+An,1X1++An,n1Xn1)

et en définissant et on obtient:A ' n , i = A * n , n A n , iBn=An,nBnAn,i=An,nAn,i

Xn=Bn+An,1X1++An,n1Xn1

et nous pouvons alors supprimer tous les besoins de dans le système en définissant, pour : i , j < nXni,j<n

A ' i , j = A i , j + A i , n A ' n , j

Bi=Bi+Ai,nBn
Ai,j=Ai,j+Ai,nAn,j

Quand on a résolu quand , on obtient une équation comme celle-ci: n = 1Xnn=1

X1=B1

sans . Ainsi, nous avons eu notre expression régulière.A1,i

L'algorithme

Grâce à cela, nous pouvons construire l'algorithme. Pour avoir la même convention que dans l'induction ci-dessus, nous dirons que l'état initial est et que le nombre d'états est . Tout d'abord, l'initialisation pour remplir : m Bq1mB

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] := ∅

et 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]

l'expression finale est alors:

e := B[1]

la mise en oeuvre

Même si cela peut sembler un système d’équations qui semble trop symbolique pour un algorithme, celui-ci est bien adapté à une implémentation. Voici une implémentation de cet algorithme dans Ocaml (lien brisé) . Notez que mis à part la fonction brzozowski, tout est à imprimer ou à utiliser pour l'exemple de Raphaël. Notez qu'il existe une fonction étonnamment efficace de simplification des expressions régulières simple_re.

jmad
la source
4
Link est mort ...
Columbo
Mise en oeuvre en Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
cakraww du
24

Méthode de fermeture transitive

Cette méthode est facile à écrire sous la forme d’un algorithme, mais génère des expressions régulières absurdement grandes et est peu pratique si vous la faites à la main, principalement parce que cela est trop systématique. C'est une solution simple et efficace pour un algorithme.

L'idée clé

Laissez représenter l'expression régulière des chaînes allant de à utilisant les états . Soit le nombre d'états de l'automate.Ri,jkqiqj{q1,,qk}n

Supposons que vous connaissiez déjà l'expression régulière de à sans l'état intermédiaire (sauf pour les extrémités), pour tout . Vous pouvez alors deviner comment l'ajout d'un autre état affectera la nouvelle expression régulière : elle ne change que si vous avez des transitions directes vers , et cela peut être exprimé de la manière suivante:Ri,jqiqjqki,jRi,jqk

Ri,j=Ri,j+Ri,k.Rk,k.Rk,j

( est et est .)RRk1RRk

Exemple

Nous allons utiliser le même exemple que dans la réponse de Raphaël . Au début, vous ne pouvez utiliser que les transitions directes.

Voici la première étape (notez qu'une boucle auto avec une étiquette aurait transformé le premier en .aε(ε+a)

R0=[εabbεaabε]

À la deuxième étape, nous pouvons utiliser (qui est renommé en pour nous, car est déjà utilisé aux fins susmentionnées). Nous verrons comment fonctionne.q0q1R0R1

De à : .q2q2R2,21=R2,20+R2,10R1,10R1,20=ε+bεa=ε+ba

Pourquoi donc? C’est parce qu’il est possible de passer de à utilisant seulement tant qu’état intermédiaire en restant ici ( ) ou en allant à ( ), en y faisant une boucle ( ) et en revenant ( ).q2q2q1εq1aεb

R1=[εabbε+baa+bbab+aaε+ab]

Vous pouvez aussi calculer comme cela et , et vous donnera l'expression finale car est à la fois initial et final. Notez que beaucoup de simplification des expressions ont été faites ici. Sinon, le premier de serait et le premier de serait .R2R3R1,131aR0(+a)aR1((+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

Fermeture 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 l'expression finale est (supposons que est l'état initial):qs

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

Mais vous pouvez imaginer que cela génère des expressions régulières laides. Vous pouvez en effet vous attendre à des choses comme qui représente le même langage que . Notez que la simplification d'une expression régulière est utile dans la pratique.a un()+(a+())(ε)(a+)aa

jmad
la source