Univ.

Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

INF 302 : Langages & Automates

Chapitre 10 : Théorème de Kleene

Yliès Falcone

[email protected] — www.ylies.fr

Univ. Grenoble-Alpes, Inria

-
Laboratoire d’Informatique de Grenoble - www.liglab.fr
Équipe de recherche LIG-Inria, Corse - team.inria.fr/corse/

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 1 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 2 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 3 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Théorème de Kleene

Théorème de Kleene
Soit Σ un alphabet et L ⊆ Σ∗ .
L est à états finis ⇔ L est régulier.
De plus :
1 Il existe un algorithme qui transforme un automate fini en une expression régulière
équivalente.
2 Inversement, il existe un algorithme qui transforme une expression régulière en un
automate fini équivalent.

(Ces algorithmes sont implémentés dans Aude.)

Démonstration : dans les deux prochaines sections

Nous allons :
montrer ce théorème de manière semi-formelle.
exhiber une procédure effective de traduction entre ces formalismes.
(L’implication de droite à gauche et le deuxième point du théorème découlent des
propriétés de fermeture des automates finis.)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 4 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Conséquences du théorème de Kleene

Soient e1 et e2 deux expressions régulières.

Décidabilité de l’inclusion des langages dénotés par des expressions régulières

Déterminer si L(e1 ) ⊆ L(e2 ) est décidable.

Décidabilité de l’équivalence d’expressions régulières

Déterminer si e1 ≡ e2 est décidable.

Remarque Il n’y a pas d’autre méthode connue pour montrer la décidabilité de ces deux
résultats (que d’utiliser le théorème de Kleene et de passer par les automates). □

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 5 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

Calcul des langages associés aux états
Élimination des états
Calcul des langages associés aux chemins
Comparaison des méthodes

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 6 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

Calcul des langages associés aux états
Élimination des états
Calcul des langages associés aux chemins
Comparaison des méthodes

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 7 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

L’idée par un exemple : trouver une relation entre les états

Soit Σ = {a, b, c} et A l’automate suivant :

a b

b
1 2

c a,c
3

On peut associer le système d’équations suivant à A :

X1 = {a} · X1 ∪ {b} · X2 ∪ {ϵ}

X2 = {b} · X2 ∪ {a, c} · X3
X3 = {c} · X1

Intuitivement, Xi décrit les mots acceptés à partir de l’état i.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 8 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

L’idée par un exemple : écrire le système d’équations

a b

b
1 2

c a,c
3

Si on utilise les expressions régulières comme notation, on peut écrire ce système

d’équations de la manière suivante :

X1 = aX1 + bX2 + ϵ
X2 = bX2 + (a + c)X3
X3 = cX1

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 9 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Système d’équations associé à un automate

Méthode de Janusz Antoni Brzozowski et Edward Joseph McCluskey, 1964

Soit A = (Q, Σ, q0 , δ, F ) un ADEF ou ANDEF.

Soit SE (A) le système d’équations donné par :

X
Xq = aXq′ + ( si q ∈ F alors ϵ sinon ∅)
δ(q,a)=q ′

Question :
Comment résoudre un tel système d’équations ?

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 10 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Résolution d’équations linéaires (lemme d’Arden)

Lemme
Soient A, B ⊆ Σ∗ des langages. Considérons l’équation :
X = AX + B

1 Le langage A∗ B est une solution de l’équation

2 (Lemme d’Arden) : Si ϵ ̸∈ A, alors A∗ B est la solution unique.

Démonstration (En TD).

1 Vérifier que A∗ B = AA∗ B + B = A · A∗ · B + ϵ · B = (AA∗ + ϵ)B.
2 Preuve par contradiction.

Attention :
Pour résoudre un système d’équations correspondant à un automate, on applique le
lemme que dans le deuxième cas.
Remarquons que, comme l’automate d’entrée est soit un ADEF ou un ANDEF (et
pas un ϵ-ANDEF), le cas 2 s’applique toujours.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 11 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Solution du système d’équations linéaires et langage de l’automate

Théorème
Soit A = (Q, Σ, q0 , δ, F ) un automate fini.
Soit (Lq | q ∈ A) la plus petite solution de SE (A).
Alors,
L(A) = LXq0 .

Le langage accepté par

a b Le langage accepté par
b b
b
1 2 a
42 52
c a,c
a
3
est L42
est L1

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 12 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple de résolution de système d’équations

a b

b
1 2

c a,c
3

Considérons le système d’équations suivant associé à l’automate ci-dessus :

X1 = aX1 + bX2 + ϵ
X2 = bX2 + (a + c)X3
X3 = cX1

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 13 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple de résolution de système d’équations

a b

b
1 2

c a,c
3

On remplace X3 par cX1 dans la deuxième équation :

X1 = aX1 + bX2 + ϵ
X2 = bX2 + (a + c)cX1
X3 = cX1

On applique le lemme d’Arden sur la deuxième équation (ϵ ∈

/ L(b) = {b})

X1 = aX1 + bX2 + ϵ
X2 = b ∗ (a + c)cX1
X3 = cX1

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 13 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple de résolution de système d’équations

a b

b
1 2

c a,c
3

On remplace X2 par b ∗ (a + c)cX1 dans la première équation :

X1 = (a + bb ∗ (a + c)c)X1 + ϵ
X2 = b ∗ (a + c)cX1
X3 = cX1

/ L(a + bb ∗ (a + c)c)) :
Et on applique le lemme d’Arden sur la première équation (ϵ ∈

X1 = (a + bb ∗ (a + c)c)∗
X2 = b ∗ (a + c)cX1
X3 = cX1

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 13 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple de résolution de système d’équations

a b

b
1 2

c a,c
3

Le langage accepté est (a + bb ∗ (a + c)c)∗ .

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 13 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 de résolution de système d’équations

b b
a
42 52
a

Considérons le système d’équations suivant associé à l’automate ci-dessus :

X42 = bX42 + aX52

X52 = bX52 + aX42 + ϵ

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 14 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 de résolution de système d’équations

b b
a
42 52
a

On applique le lemme d’Arden sur la deuxième équation (ϵ ∈

/ b)

X42 = bX42 + aX52

X52 = b ∗ (aX42 + ϵ)

On remplace X52 par b ∗ (aX42 + ϵ) dans la première équation :

X42 = bX42 + ab ∗ (aX42 + ϵ)

X52 = b ∗ (aX42 + ϵ)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 14 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 de résolution de système d’équations

b b
a
42 52
a

On simplifie et factorise la première équation :

X42 = (b + ab ∗ a)X42 + ab ∗
X52 = b ∗ (aX42 + ϵ)

/ (b + ab ∗ a)) :
On applique le lemme d’Arden sur la première équation (ϵ ∈

X42 = (b + ab ∗ a)∗ ab ∗
X52 = b ∗ (aX42 + ϵ)

Le langage accepté est (b + ab ∗ a)∗ ab ∗ .

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 14 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 bis de résolution de système d’équations

Remarque Le choix de l’équation sur laquelle on applique le lemme d’Arden influence

l’expression régulière résulat. □

b b
a
42 52
a

Considérons le système d’équations suivant associé à l’automate ci-dessus :

X42 = bX42 + aX52

X52 = bX52 + aX42 + ϵ

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 15 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 bis de résolution de système d’équations

Remarque Le choix de l’équation sur laquelle on applique le lemme d’Arden influence

l’expression régulière résulat. □

b b
a
42 52
a

On applique le lemme d’Arden sur la première équation (ϵ ∈

/ b)

X42 = b ∗ aX52
X52 = bX52 + aX42 + ϵ

On remplace X42 par b ∗ aX52 dans la deuxième équation :

X42 = b ∗ aX52
X52 = bX52 + ab ∗ aX52 + ϵ

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 15 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Exemple 2 bis de résolution de système d’équations

Remarque Le choix de l’équation sur laquelle on applique le lemme d’Arden influence

l’expression régulière résulat. □

b b
a
42 52
a

On simplifie et factorise la deuxième équation :

X42 = b ∗ aX52
X52 = (b + ab ∗ a)X52 + ϵ

/ (b + ab ∗ a)) :
On applique le lemme d’Arden sur la deuxième équation (ϵ ∈

X42 = b ∗ aX52
X52 = (b + ab ∗ a)∗ + ϵ = (b + ab ∗ a)∗

Le langage accepté est b ∗ a (b + ab ∗ a)∗ .

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 15 / 71
Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

Calcul des langages associés aux états
Élimination des états
Calcul des langages associés aux chemins
Comparaison des méthodes

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 16 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Présentation de la méthode par élimination des états

Entrée : A = (Q, Σ, q0 , ∆, F ), un ϵ-AENFD.

Sortie : eA , une expressions régulière telle que L(eA ) = L(A).

Idée :
Étiqueter les transitions par des expressions régulières.
Supprimer les états (non initiaux et finaux) en mettant à jour les transitions sans
modifier le langage.

La technique d’élimination des états nécessite un automate normalisé :

état initial sans transition entrante,
un seul état final sans transition sortante.

Phases de la méthode :
1 Normalisation
2 Élimination des états

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 17 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Normalisation - définition

Normalisation - pour l’initialisation

S’ils existent q ∈ Q et a ∈ Σ t.q. (q, a, q0 ) ∈ ∆, alors ajouter un nouvel état i à Q t.q. :
ajouter (i, ϵ, q0 ) à ∆
i est le nouvel état initial

Normalisation - pour la terminaison

Si |F | > 1 ou ils existent q ∈ F , q ′ ∈ Q et a ∈ Σ tels que (q, a, q ′ ) ∈ ∆, alors ajouter un
nouvel état f à Q t.q. :
ajouter (q, ϵ, f ) à ∆, pour tout q ∈ F ,
{f } est le nouvel ensemble d’états terminaux/finaux.

Soit (Q, Σ, i, ∆, {f }) l’automate résultant de la normalisation de A.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 18 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Normalisation - exemple 1

b b
Considérons l’automate ci-contre.
a
Cet automate n’est pas normalisé
1 2 ni pour l’initialisation ni pour la
a terminaison.
a

Normalisation - pour l’initialisation Normalisation - pour la terminaison

b b b b
a a
1 2 1 2
a a
  

i i f

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 19 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Normalisation - exemple 2

b b
a b Considérons l’automate ci-contre.
 Cet automate n’est pas normalisé
1 2 3 4
ni pour l’initialisation ni pour la
a a terminaison.
a

Normalisation - pour l’initialisation Normalisation - pour la terminaison

b b b b
a b a b
 !
1 2 3 4 1 2 3 a 4
a a a
 ! a !
a
!
i i f

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 20 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - algorithme

Soit (Q, Σ, i, ∆, {f }) l’automate résultant de la normalisation de A.

Soit Rq,q′ l’expression régulière associée à la transition entre les états q et q ′ .

Algorithme de suppression des états

EE1 Si Q = {i, f }, alors l’expression régulière associée à A est Ri,f et l’algorithme
termine. (Sinon aller à l’étape EE2.)
EE2 Choisir q ∈ Q \ {i, f }. (Aller à l’étape EE3.)
EE3 Éliminer q comme suit (EE3a + EE3b), puis aller à l’étape EE1.
EE3a Pour chaque q1 , q2 ∈ Q \ {q}, l’expression Rq1 ,q2 devient
∗
Rq1 ,q2 + Rq1 ,q · Rq,q · Rq,q2
EE3b Considérer Q \ {q} comme nouvel ensemble d’états.

Remarque L’ordre d’élimination des états influe sur la taille de l’expression finale
générée. Des heuristiques existent pour le choix (étape EE2). □

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 21 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 1

Exemple (Calcul de l’expression régulière associée à un automate par suppression des

états)
b b
a
 
i 1 2 f
a

Considérons l’automate normalisé ci-dessus.

Nous représentons les expressions régulières Ri,j sur les transitions de l’automate.
Supprimons les états 1 et 2, dans cet ordre.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 22 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 1 (suite)

Suppression de l’état 1

b b + a · b∗ · a
a
 
i 1 2 f
a

b∗ · a

b + a · b∗ · a

b∗ · a 
i 2 f

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 23 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 1 (suite)

Suppression de l’état 2

b + a · b∗ · a

b∗ · a 
i 2 f

(b∗ · a) · ( b + a · b∗ · a )∗

(b∗ · a) · ( b + a · b∗ · a )∗
i f

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 24 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 2

Exemple (Calcul de l’expression régulière associée à un automate par suppression des

états)
b b
a b

1 2 3 a 4
a
 a 

i f

Considérons l’automate normalisé ci-dessus.

Nous représentons les expressions régulières Ri,j sur les transitions de l’automate.
Supprimons les états 1, 2, 3 et 4, dans cet ordre.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 25 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 2 (suite)

Suppression de l’état 1
b

b b
a b
  + ab
i 1 a 2 3 a 4

a a 
aa

f

b b
b
a  + ab
i 2 3 a 4

a 
aa

f

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 26 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 2 (suite)

Suppression de l’état 2
b + a (aa)∗ ( + ab) b
b

a  + ab
i 2 3 4
a + a (aa)∗ ( + ab)

aa a

f 

b
b
b + a (aa)∗ ( + ab)
i 3 4
a + a (aa)∗ ( + ab)


f 

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 27 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 2 (suite)

Suppression de l’état 3
(b + a (aa)∗ (! + ab)) · b∗ · b

b (a + a (aa)∗ (! + ab)) · b∗ · b
b
b + a (aa)∗ (! + ab)
i 3 4
a + a (aa)∗ (! + ab)
!
(b + a (aa)∗ (! + ab)) · b∗ ! + (a + a (aa)∗ ! + ab) · b∗
f

(a (aa)∗ ( + ab)) b+

(b + a (aa)∗ ( + ab)) b+  + (a (aa)∗ ( + ab)) b∗

i 4 f

(b + a (aa)∗ ( + ab)) b∗

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 28 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple 2 (suite)

Suppression de l’état 4
(a (aa)∗ ( + ab)) b+

(b + a (aa)∗ ( + ab)) b+  + (a (aa)∗ ( + ab)) b∗

i 4 f

(b + a (aa)∗ ( + ab)) b∗
+
( (b + a (aa)∗ ( + ab)) b+ ) · ( (a (aa)∗ ( + ab)) b+ )∗ · (  + (a (aa)∗ ( + ab)) b∗ )

i f
(b + a (aa)∗ (! + ab)) b∗
+
( (b + a (aa)∗ (! + ab)) b+ ) · ( (a (aa)∗ (! + ab)) b+ )∗ · ( ! + (a (aa)∗ (! + ab)) b∗ )

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 29 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

Calcul des langages associés aux états
Élimination des états
Calcul des langages associés aux chemins
Comparaison des méthodes

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 30 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

L’idée intuitive

Algorithme de McNaughton et Yamada (1960). 1

Associer une expression régulière décrivant le langage entre deux états i et j.

Induction : on se donne un numéro d’état n maximal pour les états intermédiaires :
initialisation : on s’interdit de passer par tous les états,
pas d’induction : on autorise un nouvel état intermédiaire dans les chemins et on calcul
les chemins où l’état n + 1 est autorisé en fonction des chemins ou au plus l’état n est
autorisé.
L’expression régulière finale est celle décrivant :
l’union des chemins depuis l’état initial vers un état accepteur,
n’ayant aucun état interdit.

Théorème
Soit A un ADEF, alors :
il existe une expression régulière e telle que L(e) = L(A),
il existe un algorithme de construction de e.

1. Robert McNaughton et Hisao Yamada, « Regular expressions and state graphs for automata », IRE Trans.
Electronic Computers, 1960.
Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 31 / 71
Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Preuve

Soit A = (Q, Σ, qinit , δ, F ) un AEFD.

L’idée
Construire une collection d’expressions régulières qui décrivent progressivement des
chemins de moins en moins contraints dans l’automate, par induction.

Début de la démonstration
Supposons, quitte à utiliser une fonction de renommage, que les états sont
numérotés de 1 à n (ce qui est possible car il y a un nombre fini d’états).
k
Soit Ri,j l’expression régulière des mots étiquettes d’un chemin entre l’état i et l’état
j qui passe uniquement par des états intermédiaires plus petits que k.
Il n’y a aucune contrainte sur i et j.
L’expression régulière de l’automate est :
X n
R1,f
f ∈F

k
Nous allons calculer les Ri,j pour k = 0, . . . , n.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 32 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

0
Calcul de Ri,j

0
Ri,j est l’expression régulière des chemins entre l’état i et l’état j dont tous les états
intermédiaires ont un numéro plus petit que 0 ;
,→ c’est-à-dire qui n’ont aucun état intermédiaire.

Intéressons nous aux chemins directs entre un état i et un état j : il y a deux cas
possibles.

Si i ̸= j, alors on regarde les transitions directes entre i et j :

Il n’y a pas de transition :
0
Ri,j = ∅.
Il y a une transition étiquetée par un symbole a :
0
Ri,j = a.
Il y a plusieurs transitions étiquetées par des symboles a1 , . . . , an :
0
Ri,j = a1 + . . . + an .
Sinon (i = j), les cas précédents s’appliquent de la même manière.
Il faut de plus ajouter ϵ à chaque expression régulière.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 33 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

k
Illustration de Ri,j
Première possibilité concernant le positionnement de i et j par rapport à k

k k

1 1
états
0 0

chemins

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 34 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

k
Illustration de Ri,j
Seconde possibilité concernant le positionnement de i et j par rapport à k

k k

1 1
états
0 0

chemins

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 35 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

k
Illustration de Ri,j
Un chemin ne passe pas obligatoirement par l’état k (quelque soit le positionnement de i et j par rapport à k)

k k

1 1
états
0 0

chemins

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 36 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

k
Calcul de Ri,j

Résumons :
Le positionnement de i et j peut être quelconque par rapport à k : la contrainte
k
reliée à Ri,j ne porte que sur les états intermédiaires.
k
Un chemin dans Ri,j peut passer par l’état k, ou non.
k k−1
Exprimons maintenant Ri,j en fonction de Ri,j .
k
Considérons un chemin de Ri,j :
k−1
Soit il ne passe pas par l’état k, alors c’est un chemin de Ri,j .
Soit il passe par l’état k (au moins une fois). On peut décomposer le chemin en
chemins qui ne passent pas par un état intermédiaire plus grand que k − 1.
k−1 k−1 ∗ k−1
Ri,k Rk,k Rk,j (un chemin qui passe 2
i k k j fois par k)

k k−1 k−1 k−1 k−1 ∗

Ri,j = Ri,j + Ri,k · Rk,k · Rk,j

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 37 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Application de la méthode

Étapes du calcul de l’expression régulière d’un automate - méthode des chemins

1 Renommer les chemins de l’automate pour qu’ils soient numérotés de 1 à n, où |Q|.
0
2 Calculer Ri,j .
k k
3 Calculer les Ri,j , k = 1, . . . , |Q| en utilisant l’expression récursive de Ri,j :
k k−1 k−1 k−1 k−1 ∗
Ri,j = Ri,j + Ri,k · Rk,k · Rk,j
P |Q|
4 L’expression régulière de l’automate est f ∈F
R1,f .

|Q|−1 |Q|
Remarque En pratique, on arrêtera le calcul à Ri,j et calculera les R1,f , pour f ∈ F
au besoin. □

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 38 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode des chemins : exemple 1

Soit Σ = {a, b} et A l’automate suivant :

b b
a
42 52
a

1 0 0 0 ∗ 0
0
Calcul des Ri,j Calcul des Ri,j = Ri,j + Ri,1 · (R1,1 ) · R1,j
0
R1,1 =b+ϵ 0
R2,1 =a 1
R1,1 = b∗
1
R2,1 = a · b∗
1
0
R1,2 =a 0
R2,2 =b+ϵ 1
R1,2 = b∗ · a R2,2 =
b + a · b∗ · a

2 1 1 1 ∗ 1
Calcul de R1,2 = R1,2 + R1,2 · (R2,2 ) · R2,2
2
R1,2 = (b ∗ · a) + (b ∗ · a) · (b + a · b ∗ · a)∗ · (b + a · b ∗ · a)
= (b ∗ · a) + (b ∗ · a) · (b + a · b ∗ · a)+
= (b ∗ · a) · (b + a · b ∗ · a)∗

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 39 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode des chemins : exemple 2

Soit Σ = {a, b, c} et A l’automate suivant :

a b

b
1 2

c a,c
3

0
Calcul des Ri,j
0 0 0
R1,1 =a+ϵ R2,1 =∅ R3,1 =c
0 0 0
R1,2 =b R2,2 =b+ϵ R3,2 =∅
0 0 0
R1,3 =∅ R2,3 =a+c R3,3 =ϵ

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 40 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode des chemins : exemple 2 (suite)

0
Ri,j
0 0 0
R1,1 =a+ϵ R2,1 =∅ R3,1 =c
0 0 0
R1,2 =b R2,2 =b+ϵ R3,2 =∅
0 0 0
R1,3 =∅ R2,3 =a+c R3,3 =ϵ

1 0 0 0 0 ∗
Calcul des Ri,j = Ri,j + Ri,1 · R1,1 · R1,j
1
R1,1 = a∗ 1
R2,1 =∅ 1
R3,1 = c · a∗
1
R1,2 = a∗ b 1
R2,2 =b+ϵ 1
R3,2 = c · a∗ · b
1 1 1
R1,3 =∅ R2,3 =a+c R3,3 =ϵ

2 1 1 1 1 ∗
Calcul des Ri,j = Ri,j + Ri,2 · R2,2 · R2,j
2
R1,1 = a∗ 2
R2,1 =∅ 2
R3,1 = c · a∗
2
R1,2 = a∗ · b + 2
R2,2 = b∗ 2
R3,2 = c · a∗ · b +
∗ ∗
2
R1,3 +
= a · b · (a + c) 2
R2,3 = b · (a + c) 2
R3,3 = ϵ + c · a∗ · b + · (a + c)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 41 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode des chemins : exemple 2 (fin)

Soit Σ = {a, b, c} et A l’automate suivant :

a b

b
1 2

c a,c
3

Expression régulière de A
3
R1,1 = a∗ + (a∗ · b + · (a + c)) · (ϵ + c · a∗ · b + · (a + c))∗ · c · a∗
3
R1,1 = a∗ + (a∗ · b + · (a + c)) · (c · a∗ · b + · (a + c))∗ · c · a∗
Cette expression régulière est équivalente à :

a∗ · (b + · (a + c) · c · a∗ )∗

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 42 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

Calcul des langages associés aux états
Élimination des états
Calcul des langages associés aux chemins
Comparaison des méthodes

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 43 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Méthode par élimination des états

Élimination des états - exemple

Méthode associant des équations aux états

+ élégance
+ génère des expressions régulières raisonnablement compacte
- pas aussi simple à implémenter que les autres méthodes

Méthode par élimination des états

+ intuitive
+ pratique pour la vérification manuelle

Méthode associant des équations aux chemins

+ implémentation claire et simple
- fastidieux manuellement
- tendance à créer des expressions régulières très longues

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 44 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

Méthode compositionnelle
Méthode par calcul des dérivées

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 45 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

Méthode compositionnelle
Méthode par calcul des dérivées

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 46 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

L’idée

Objectif :
Montrer que tout langage décrit par une expression régulière peut être reconnu par un
automate
,→ pour chaque expression régulière e, on peut trouver un automate A tel que

L(e) = L(A)

,→ les langages réguliers sont des langages à états

Automates construits
Les automates que nous allons construire sont des ϵ-ANDEF tels que :
un seul état accepteur,
pas de transition depuis l’état acepteur,
pas de transition vers l’état initial.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 47 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Les langages réguliers sont des langages à états

Théorème : Les langages réguliers sont des langages à états

Tout langage reconnu par une expression régulière peut être défini/reconnu par un
automate à état fini.

Induction sur les expressions régulières

éléments de bases : ϵ, symboles seuls, ∅
expressions composées : union, concaténation, fermeture
(en fonction d’automates définis pour les opérandes)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 48 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Les langages réguliers sont des langages à états

Élements de base

Mot vide (ϵ)

Symboles seuls (a ∈ Σ)

Ensemble vide (∅)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 49 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Les langages réguliers sont des langages à états

Élements composés

e1 + e2

ϵ
ϵ

ϵ ϵ

e1 · e2

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 50 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Les langages réguliers sont des langages à états

Élements composés (suite)

e∗

ϵ
ϵ
ϵ

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 51 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Traduction des expressions régulières vers automates à états finis

Exemple (Traduction des expressions régulières vers ϵ-ANDEF)

0+1
(0 + 1)∗
(0 + 1)∗ · 1
(0 + 1)∗ · 1 · (0 + 1)

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 52 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

Méthode compositionnelle
Méthode par calcul des dérivées

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 53 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Introduction de la méthode

Introduite par J. Brzozowski (notion de dérivée) (1964) et Antimirov (notions de dérivées

partielles) (1996).

Méthode purement algébrique ne nécessitant pas de construction explicite de l’automate.

Méthode fonctionne par calcul de la dérivée d’une expression régulière pour laquelle on
veut construire un automate.

Intuitivement, la dérivée d’une expression régulière e sur un symbole a est une expression
régulière décrivant ce qu’il manque après avoir lu a pour former un mot de e.

Avantage de la méthode :
travaille uniquement sur la syntaxe des expressions régulières
peut se faire “à la volée"

Soit Σ un alphabet (utilisé dans la suite pour construire des expressions régulières).

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 54 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Préliminaire : terme constant d’une expression régulière

Opérateur qui indique si ϵ appartient au langage dénoté par une expression régulière.

Définition (Terme constant d’une expression régulière)

Le terme constant d’une expression régulière est une expression régulière donnée par la
fonction c : ER → {ϵ, ∅} définie par :

ϵ si ϵ ∈ L(e)
c(e) =
∅ sinon
Afin de pouvoir être calculer directement à partir de l’expression régulière, le terme
constant peut être également défini inductivement par :
c(∅) = ∅ c(a) = ∅, pour a ∈ Σ c(e · e ′ ) = c(e) · c(e ′ )
′ ′
c(ϵ) = ϵ c(e + e ) = c(e) + c(e ) c(e ∗ ) = ϵ

Exemple (Terme constant d’expressions régulières sur Σ = {a, b})

c(a) = ∅. c(a∗ ) = ϵ. c(a · b) = ∅. c(a · b)∗ = ϵ.

Remarque Calculer le terme constant suppose de simplifier l’expression régulière

résultat (dans le cas où il est calculé pour des expressions régulières composées). □

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 55 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Dérivée d’une expression régulière par rapport à un symbole

Rappel : intuitivement, la dérivée d’une expression régulière e sur un symbole a est une
expression régulière décrivant ce qu’il manque après avoir lu a pour former un mot de e.

Définition (Dérivée d’une expression régulière : une première définition)

∂
La dérivée de e ∈ ER sur a ∈ Σ est l’expression régulière notée ∂a
e et dénotant le langage
∗
{w ∈ Σ | a · w ∈ L(e)} .

Nous donnons la précédence à l’opérateur de dérivation par rapport aux autres opérateurs.

Exemple (Dérivée d’une expression régulière)

∂ ∂
∂a a = ϵ ∂a (a · b) = b
∂
∂a ϵ = ∅
∂
∂a (a + b) =ϵ ∂
∂a (a · b)∗ = b · (a · b)∗

Comment calculer la dérivée d’une expression régulière quelconque ?

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 56 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Dérivée d’une expression régulière par rapport à un symbole

Définition (Dérivée d’une expression régulière : définition inductive (pour le calcul))

La dérivée par rapport à un symbole a ∈ Σ est définie inductivement sur la syntaxe des
expressions régulières par :
∂
∂a ∅ = ∅
∂
∂a (e + e′) = ∂
∂a e + ∂ ′
∂a e
∂
∂a ϵ = ∅
∂
∂
∂a (e · e′) = ∂
∂a e · e ′ + c(e) · ∂ ′
∂a e
∂a a = ϵ
∂ ∗
∂
∂a b = ∅, lorsque b ̸= a ∂a e = ∂
∂a e · e∗

Exemple (Dérivée d’une expression régulière par rapport un symbole)

∂ ∂ ∂ ∂
∂a a = ϵ · b) = ∂a
∂a (a a · b + c(a) · ∂a b =
∂ ϵ·b+∅·∅=b
∂a ϵ = ∅
∗
∂ ∂ ∂
∂
∂a (ab) = ∂
∂a (ab) · (a · b)∗ =
∂a (a + b) = ∂a a + ∂a b = ϵ+∅ = ϵ
b · (a · b)∗

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 57 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Dérivée d’une expression régulière par rapport à un mot

Intuitivement, dériver par rapport à un mot consiste à dériver récursivement et par

rapport à chaque lettre du mot dans l’ordre de lecture de ce mot.

Définition (Dérivée d’une expression régulière par rapport à un mot)

La dérivée par rapport à un mot dans Σ∗ est défini inductivement sur les mots par

∂ ∂ ∂ ∂
∂ϵ e =e ∂a·u e = ∂u dea, avec dea = ∂a e

Exemple (Dérivée d’une expression régulière par rapport à un mot)

∂
∂ab ab = ϵ
∂ ∗∂ ∂ ∗
∂a·b (a · b)
= ∂b ∂a (a · b)
On a vu que ∂a (a · b)∗ = b · (a · b)∗ .
∂

∂
Donc ∂
∂a·b (a · b)∗ = ∂
∂b b · (a · b)∗ = b ·(a · b)∗ + c(b) · ∂b
∂
(a · b)∗ = (a · b)∗
∂b
|{z} |{z}
ϵ ∅

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 58 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Construction d’un automate par la dérivée d’une expression régulière

Intuition

Utiliser des expressions régulières pour les états de l’automate.

On passe d’un état à l’autre sur un symbol en calculant sa dérivée sur ce symbole.
La dérivée d’une expression régulière représente "ce qu’il reste à lire" après avoir lu
un symbole pour reconnaître l’expression qu’on a dérivée.
L’état initial contient l’expression régulière pour laquelle on construit l’automate.
Un état q est terminal s’il ne reste plus qu’à lire ϵ, cad si c(q) = ϵ.

∂r
∂a
a

init r

b
∂r
∂b

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 59 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Construction d’un automate par la dérivée d’une expression régulière

Définition de l’automate

Finitude de l’ensemble des dérivées

L’ensemble des dérivées d’une expression régulière est fini modulo associativité,
commutativité et idempotence des opérateurs.

Démonstration.
Admis.

Soit e ∈ ER une expression régulière définie sur un alphabet Σ et ∂e ∈ P(ER) l’ensemble

des (expressions régulières) dérivées.

Définition (Automate des dérivées)

L’automate dérivée de e est l’AEFD (∂e, Σ, e, δe , Fe ) avec :
∂
δe (d, a) = ∂a
d, pour d ∈ ∂e et a ∈ Σ,
Fe = {d ∈ ∂e | c(d) = ϵ}.

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 60 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Construction d’un automate par la dérivée d’une expression régulière

Exemple de construction de l’automate

Exemple (Construction de l’automate pour l’expression régulière (a · b)∗ )

On a vu que :
a
∂
∂a
(a · b)∗ = b · (a · b)∗
∂
∂a·b
(a · b)∗ = (a · b)∗ (a · b)∗ b · (a · b)∗
De plus, nous avons :
∂
∂b
(a · b)∗ = ∅ b
∂
∂b
(b · (a · b)∗ = (a · b)∗
b
Par ailleurs : a
∗
c((a · b) ) = ϵ
c(b · (a · b)∗ ) = ∅ ∅
c(∅) = ∅

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 61 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 62 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Analyse lexicale

Distinction entre la syntaxe (les phrases) et le lexique (les mots)

Spécification des mots du langage du langage de programmation

Exemple (Lexique d’un langage de programmation)

identificateurs
constantes entières
l’opérateur “+"
mots clés du langage

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 63 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Analyse lexicale

Entrée : sequence de caractères

Sortie : sequence de classes d’unités lexicales (∼ séquence de mots)
1 Calcul de la plus grand séquence parmi un ensemble de classes lexicales
,→ lexemes du programme
2 Insertion d’ une référence dans la table des symboles pour les identificateurs.
3 Retour à l’analyseur syntaxique :
la classe lexicale (token) : constantes, identificateurs, mots clés, opérateurs,
separateurs, . . .
l’élement associé à cette classe : le lexeme
4 Suppression des éléments hors du langage (espaces, commentaires, retours à la ligne,
tabulations)
5 Token special : error – lorsque les règles du lexique ne sont pas respectées.
Basé sur des outils formels : les langages réguliers
décrits par des expressions régulières
reconnus par des automates à états finis (déterministes)
Exemple d’analyseur lexicale : LeX (générateur de code implémentant des automates à
partir d’expressions régulières)
Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 64 / 71
Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Une calculette avec deux opérations

Spécification du lexique

Syntaxe (grammaire hors-contexte) :

E : E + T | T
T : T * F | F
F : ID | NUM |(E)

Lexique
opérateurs : {+, ∗}
séparateurs : ( )
une constante entière NUM
un identificateur ID

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 65 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Une calculette avec deux opérations

Expressions régulières et automates reconnaisseurs pour le lexique

+ [a-z][a-zA-Z0-9]*
+
a-z,A-Z

* a-z
*

( 0-9
(
[1-9][0-9]*
0-9
)
) 1-9

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 66 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

LeX : un générateur d’analyseurs lexicaux

Outil de génération d’analyseurs lexicaux écrits en langage C

Spécifications en LeX
déclarations
%%
règles
%%
procédures

Règles
modele1 {action1}
...
modele2 {action2}

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 67 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

LeX : un générateur d’analyseurs lexicaux

Exemple

Exemple (Règles)
1 Suppression des espaces redondants
%%
[ \t]+ printf(" ");
%%
yywrap(){return(1);}
2 Reconnaissance d’un entier
integer {digit}+
%%
{integer} {attribut=atoi(yytext);return(Integer);}

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 68 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Plan Chap. 8 - Expressions Régulières / Théorème de Kleene

1 Théorème de Kleene

2 Des automates vers les expressions régulières

3 Des expressions régulières vers les automates

4 Application en informatique : analyse lexicale

5 Résumé

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 69 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Résumé I

Théorème de Kleene et ses conséquences.

Traduction des automates vers les expressions régulières :
Méthode associant des équations aux états (langages associés aux états) :
Équations associées aux états d’un automate
Lemme d’Arden
Méthode par suppression des états
Méthode associant des équations aux (langages associés aux chemins)
Traduction des expressions régulières vers les automates
Méthode compositionnelle
Méthode par calcul des dérivées
Application en informatique : analyse lexicale en compilation

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 70 / 71

Univ. Grenoble Alpes, Département Licence Sciences et Technologies, Licence deuxième année

Résumé II

Id
/≈ ADEF ANDEF
Det
Id Id

Det ◦ ` `
-ANDEF

équations équations
constr.
+ Arden + Arden
compo.

ER
ADEF : automate déterministe /≈ : minimisation
ANDEF : automate non-déterministe Id : identité
-ANDEF : automate non-déterministe Det : déterminisation
avec -transitions ` : élimination des -transitions
ER : expressions régulières constr. compo : construction compositionnelle

Y. Falcone (UGA - Inria) INF 302 : Langages & Automates 71 / 71