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

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 $p,q,r$$e,f,g,h,i$$q$

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

Exemple

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

on enlève successivement :$q_2$

et ensuite :$q_3$

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 $q_1$$q_1$

Algorithme

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

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 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 )$∅$$ε$$q_i$$q_k$$q_j$$q_k$

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:$q_f$$q_s$

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)$$e_{s,f}$$s$$f$$e_{s,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.

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'équation$A= (Q,\Sigma,\delta,q_0,F)$$\varepsilon$$q_i$

$\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ù 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.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

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 ¹:$\cup$$\cdot$$\cup$

Laissez langues régulières avec . Ensuite,$L,U,V \subseteq \Sigma^*$$\varepsilon \notin U$

$\qquad \displaystyle L = UL \cup V \quad \Longleftrightarrow \quad L = U^*V$

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.$Q_i$$q_i$$Q_i$$A$$q_i$$Q_0$$q_0$

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:

^{[ 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 seconde:

$\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 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 = Q_1$$U = ab$$V = (b \cup aa) \cdot Q_0$$\varepsilon \notin U = \{ab\}$

$\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{(by Arden's Lemma)} \end{align}$

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

$\qquad \displaystyle ((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 .

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=A^*B$$X=AX∪B$

nous pouvons résoudre ce problème par induction sur en mettant à jour les tableaux et conséquence. A l'étape , on a:$n$$A_{i,j}$$B_{i,j}$$n$

et la règle d'Arden nous donne:

et en définissant et on obtient:A ' n , i = A * n , n A n , $B'_n = A_{n,n}^* B_n$$A'_{n,i}=A_{n,n}^*A_{n,i}$

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

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

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

sans . Ainsi, nous avons eu notre expression régulière.$A'_{1,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 $q_1$$m$$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] := ∅

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.

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.$R^k_{i,j}$$q_i$$q_j$$\{q_1, …, q_k\}$$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:$R_{i,j}$$q_i$$q_j$$q_k$$i,j$$R'_{i,j}$$q_k$

( est et est .)$R$$R^{k-1}$$R'$$R^k$

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)$

À 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.$q_0$$q_1$$R^0$$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$

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 ( ).$q_2$$q_2$$q_1$$ε$$q_1$$a$$ε^*$$b$

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 .$R^2$$R^3$$R^3_{1,1}$$1$$a$$R^0$$(∅+a)$$a$$R^1$$((∅+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):$q_s$

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 $(∅)^*+(a+(∅)^*)(ε)^*(a + ∅)$$aa$