Algorithme de Kleene - Kleene's algorithm
En informatique théorique , en particulier en théorie du langage formel , l'algorithme de Kleene transforme un automate fini non déterministe (NFA) donné en une expression régulière . Avec d'autres algorithmes de conversion, il établit l'équivalence de plusieurs formats de description pour les langues régulières . Des présentations alternatives de la même méthode incluent la "méthode d'élimination" attribuée à Brzozowski et McCluskey , l'algorithme de McNaughton et Yamada et l'utilisation du lemme d' Arden .
Description de l'algorithme
Selon Gross et Yellen (2004), l'algorithme peut être retracé jusqu'à Kleene (1956). Une présentation de l'algorithme dans le cas des automates finis déterministes (DFA) est donnée dans Hopcroft et Ullman (1979). La présentation de l'algorithme pour les NFA ci-dessous suit Gross et Yellen (2004).
Étant donné un automate fini non déterministe M = ( Q , Σ, δ, q 0 , F ), avec Q = { q 0 , ..., q n } son ensemble d' états , l'algorithme calcule
- les ensembles R k
ij de toutes les chaînes qui prennent M de l'état q i à q j sans passer par un état numéroté supérieur à k .
Ici, «passer par un état» signifie y entrer et en sortir, donc i et j peuvent être supérieurs à k , mais aucun état intermédiaire ne le peut. Chaque ensemble R k
ij est représenté par une expression régulière; l'algorithme les calcule pas à pas pour k = -1, 0, ..., n . Puisqu'il n'y a pas d'état numéroté plus haut que n , l'expression régulière R n
0j représente l'ensemble de toutes les chaînes qui prennent M de son état de départ q 0 à q j . Si F = { q 1 , ..., q f } est l'ensemble des états d'acceptation , l' expression régulière R n
01 | ... | R n
0f représente la langue acceptée par M .
Les expressions régulières initiales, pour k = -1, sont calculées comme suit pour i ≠ j :
-
R −1
ij = a 1 | ... | a m où q j ∈ δ ( q i , a 1 ), ..., q j ∈ δ ( q i , a m )
et comme suit pour i = j :
-
R −1
ii = a 1 | ... | un m | ε où q i ∈ δ ( q i , a 1 ), ..., q i ∈ δ ( q i , a m )
En d'autres termes, R −1
ij mentionne toutes les lettres qui marquent une transition de i à j , et nous incluons également ε dans le cas où i = j .
Après cela, à chaque étape, les expressions R k
ij sont calculés à partir des précédents par
-
R k
ij = R k -1
ik ( R k -1
kk ) * R k -1
kj | R k -1
ij
Une autre façon de comprendre le fonctionnement de l'algorithme est comme une "méthode d'élimination", où les états de 0 à n sont successivement supprimés: lorsque l'état k est supprimé, l'expression régulière R k -1
ij , qui décrit les mots qui étiquettent un chemin de l'état i > k à l'état j > k , est réécrit dans R k
ij afin de prendre en compte la possibilité de passer par l'état "éliminé" k .
Par récurrence sur k , on peut montrer que la longueur de chaque expression R k
ij est au plus 1 / 3 (4 k +1 (6 s +7) - 4) symboles, où s désigne le nombre de caractères dans Σ. Par conséquent, la longueur de l'expression régulière représentant le langage accepté par M est au plus 1 / 3 (4 n +1 (6 s +7) f - f - 3) symboles, où f désigne le nombre d'états finaux. Cette explosion exponentielle est inévitable, car il existe des familles de DFA pour lesquelles toute expression régulière équivalente doit être de taille exponentielle.
En pratique, la taille de l'expression régulière obtenue en exécutant l'algorithme peut être très différente selon l'ordre dans lequel les états sont considérés par la procédure, c'est-à-dire l'ordre dans lequel ils sont numérotés de 0 à n .
Exemple
L'automate montré dans l'image peut être décrit comme M = ( Q , Σ, δ, q 0 , F ) avec
- l'ensemble des états Q = { q 0 , q 1 , q 2 },
- l'alphabet d'entrée Σ = { a , b },
- la fonction de transition δ avec δ ( q 0 , a ) = q 0 , δ ( q 0 , b ) = q 1 , δ ( q 1 , a ) = q 2 , δ ( q 1 , b ) = q 1 , δ ( q 2 , a ) = q 1 , et δ ( q 2 , b ) = q 1 ,
- l'état de départ q 0 , et
- ensemble d'états d'acceptation F = { q 1 }.
L'algorithme de Kleene calcule les expressions régulières initiales comme
R −1
00= a | ε R −1
01= b R −1
02= ∅ R −1
10= ∅ R −1
11= b | ε R −1
12= a R −1
20= ∅ R −1
21= a | b R −1
22= ε
Après cela, le R k
ij sont calculés à partir du R k -1
ij pas à pas pour k = 0, 1, 2. Les
égalités d' algèbre de Kleene sont utilisées pour simplifier autant que possible les expressions régulières.
- Étape 0
R 0
00= R −1
00 ( R −1
00 ) * R −1
00 | R −1
00= ( a | ε) ( a | ε) * ( a | ε) | a | ε = a * R 0
01= R −1
00 ( R −1
00 ) * R −1
01 | R −1
01= ( a | ε) ( a | ε) * b | b = a * b R 0
02= R −1
00 ( R −1
00 ) * R −1
02 | R −1
02= ( a | ε) ( a | ε) * ∅ | ∅ = ∅ R 0
10= R −1
10 ( R −1
00 ) * R −1
00 | R −1
10= ∅ ( a | ε) * ( a | ε) | ∅ = ∅ R 0
11= R −1
10 ( R −1
00 ) * R −1
01 | R −1
11= ∅ ( a | ε) * b | b | ε = b | ε R 0
12= R −1
10 ( R −1
00 ) * R −1
02 | R −1
12= ∅ ( a | ε) * ∅ | une = a R 0
20= R −1
20 ( R −1
00 ) * R −1
00 | R −1
20= ∅ ( a | ε) * ( a | ε) | ∅ = ∅ R 0
21= R −1
20 ( R −1
00 ) * R −1
01 | R −1
21= ∅ ( a | ε) * b | a | b = a | b R 0
22= R −1
20 ( R −1
00 ) * R −1
02 | R −1
22= ∅ ( a | ε) * ∅ | ε = ε
- Étape 1
R 1
00= R 0
01 ( R 0
11 ) * R 0
10 | R 0
00= a * b ( b | ε) * ∅ | a * = a * R 1
01= R 0
01 ( R 0
11 ) * R 0
11 | R 0
01= a * b ( b | ε) * ( b | ε) | a * b = a * b * b R 1
02= R 0
01 ( R 0
11 ) * R 0
12 | R 0
02= a * b ( b | ε) * une | ∅ = a * b * ba R 1
10= R 0
11 ( R 0
11 ) * R 0
10 | R 0
10= ( b | ε) ( b | ε) * ∅ | ∅ = ∅ R 1
11= R 0
11 ( R 0
11 ) * R 0
11 | R 0
11= ( b | ε) ( b | ε) * ( b | ε) | b | ε = b * R 1
12= R 0
11 ( R 0
11 ) * R 0
12 | R 0
12= ( b | ε) ( b | ε) * une | une = b * a R 1
20= R 0
21 ( R 0
11 ) * R 0
10 | R 0
20= ( a | b ) ( b | ε) * ∅ | ∅ = ∅ R 1
21= R 0
21 ( R 0
11 ) * R 0
11 | R 0
21= ( a | b ) ( b | ε) * ( b | ε) | a | b = ( a | b ) b * R 1
22= R 0
21 ( R 0
11 ) * R 0
12 | R 0
22= ( a | b ) ( b | ε) * une | ε = ( a | b ) b * a | ε
- Étape 2
R 2
00= R 1
02 ( R 1
22 ) * R 1
20 | R 1
00= a * b * ba (( a | b ) b * a | ε) * ∅ | a * = a * R 2
01= R 1
02 ( R 1
22 ) * R 1
21 | R 1
01= a * b * ba (( a | b ) b * a | ε) * ( a | b ) b * | a * b * b = a * b ( a ( a | b ) | b ) * R 2
02= R 1
02 ( R 1
22 ) * R 1
22 | R 1
02= a * b * ba (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | a * b * ba = a * b * b ( a ( a | b ) b * ) * a R 2
10= R 1
12 ( R 1
22 ) * R 1
20 | R 1
10= b * a (( a | b ) b * a | ε) * ∅ | ∅ = ∅ R 2
11= R 1
12 ( R 1
22 ) * R 1
21 | R 1
11= b * a (( a | b ) b * a | ε) * ( a | b ) b * | b * = ( a ( a | b ) | b ) * R 2
12= R 1
12 ( R 1
22 ) * R 1
22 | R 1
12= b * a (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | b * a = ( a ( a | b ) | b ) * a R 2
20= R 1
22 ( R 1
22 ) * R 1
20 | R 1
20= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ∅ | ∅ = ∅ R 2
21= R 1
22 ( R 1
22 ) * R 1
21 | R 1
21= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * ( a | b ) b * | ( a | b ) b * = ( a | b ) ( a ( a | b ) | b ) * R 2
22= R 1
22 ( R 1
22 ) * R 1
22 | R 1
22= (( a | b ) b * a | ε) (( a | b ) b * a | ε) * (( a | b ) b * a | ε) | ( a | b ) b * a | ε = (( a | b ) b * a ) *
Puisque q 0 est l'état de départ et q 1 est le seul état d'acceptation, l'expression régulière R 2
01 désigne l'ensemble de toutes les chaînes acceptées par l'automate.
Voir également
- Algorithme Floyd – Warshall - un algorithme sur des graphes pondérés qui peut être implémenté par l'algorithme de Kleene en utilisant une algèbre de Kleene particulière
- Problème de hauteur d'étoile - quelle est la profondeur d'imbrication minimale des étoiles de toutes les expressions régulières correspondant à un DFA donné?
- Problème généralisé de hauteur d'étoile - si un opérateur de complément est autorisé en plus dans les expressions régulières, la profondeur d'imbrication des étoiles de la sortie de l'algorithme de Kleene peut-elle être limitée à une borne fixe?
- L'algorithme de construction de Thompson - transforme une expression régulière en un automate fini