Plan

Ø Concepts de base

Théorie des Ø Expression régulière

Ø Automate à état finis

Langages
Ø Déterminisation d’automate (NFAàDFA)
Ø Transformation d’une Expression régulière en automate
Ø Transformation DFA en Expression régulière
Ø Minimisation d’une Expression régulière
Ø Minimisation d’un automate

Pr. Youness Tabii

Alphabet
vUn Alphabet est un ensemble fini de symboles indivisibles (lettres,
séparateurs, chiffres,…).

vNous désignerons par å ou A les alphabets dénotant le vocabulaire

Concepts de base
d‘un langage.
vPar exemple, le vocabulaire des chiffres est : å = {0,1,2,3,4,5,6,7,8,9}.

vDans un langage, nous utilisons un alphabet pour construire des mots

(w) : w Í å* ou w Í A*.
vPar exemple un nombre est un mot de chiffre. å* = {..., 11, 12, 13, …}.
Langage Langage
v |w| = longueur du mot w.
v L’ensemble de tous les mots construits sur un v Le mot de longueur zéro est noté e. e est le mot
alphabet sera noté par å*. vide, il est neutre pour la concaténation des
v Un langage est un ensemble de mots construit langages.
sur un alphabet (å ou A). v Ordre partiel sur les mots :
v a est préfixe de b si $a’, tel que b = aa’
v Tout langage défini sur un alphabet å (ou A) sera
une partie de å* (ou A*). v a est suffixe de b si $a’, tel que b = a’a
v a est sous mot de b si b = b0a0b1a1 …. bnan avec bi et ai Î
å* pour a = a0a1 … an

Langage
Opérations sur les langages : Soit L1 et L2 deux
langages sur å* :
Les Expressions
v Union : L1 ∪ L2 {a | a Î L1 ou a Î L2}
v Intersection : L1 ∩ L2 {a | a Î L1 et a Î L2} Régulières
v Différence : L1/L2 {a | a Î L1 et a Ï L2}
v Complément : L2 {a Î L1| a Ï L2}
v Concaténation : L1L2 {ab| a Î L1 et b Î L2}
Définition Besoins d’ER
vLes Expressions Régulières (ER) sont des motifs destinés à décrire des L’utilisation des ER peuvent comprendre :
chaînes ou des sections complètes de texte.
ü La recherche d’éléments dans un texte (ou un flux de
données) : Il s’agit de reconnaître des éléments
vLes motifs sont construits selon une syntaxe simple qui permet de particuliers.
décrire de manière abstraite les caractéristiques d’une chaîne de
caractères. ü L’extraction d’information : Il s’agit d’isoler des parties
d’une chaîne de caractères.
ü La validation de données : Il s’agit de vérifier la validité
vLa syntaxe d’une expression régulière comporte des règles et des d’une information.
symboles spéciaux appelés méta-caractères.
ü La substitution et le reformatage : il s’agit de
reconnaître un texte pour le réécrire en un autre.
vLe mot Régulière doit être compris dans le sens qui obéit aux règles.

Exemple Exemple
Exemple d’une ER de validation des variables en C : Exemple d’une ER de validation des variables en C :
Soit : L(L+S+C)*
Ø L un ensemble fini de lettres,
Ø S un ensemble fini de séparateurs (ensemble valide du
langage), Ø Le + représente la sélection (disjonction), elle peut se noter |,
ou…
Ø C l’ensemble fini des entiers de 0 à 9.
Ø Alors l’expression régulière des variables valides en langage Ø Le * signifie 0 ou plusieurs occurrences de la sous-expression.
C qui vérifie qu’une Ø La juxtaposition des symboles du vocabulaire, ici la
variable commence par une Lettre
Ø
juxtaposition de L et () représente leur concaténation.
Ø puis peut comporter des Lettres, des séparateurs ou des chiffres
Ø Les parenthèses, ( et ) représentent les groupements des sous-
L(L+S+C)* expressions.
Exemple ER - Langage
Exemple de construction (mot d’un langage) : v Un Langage rationnel est un langage reconnue par une
expression régulière (expression rationnelle).
vL’ER a+b dénote le langage {a, b} pour un alphabet S constitué v Un langage L Í å* est rationnel s'il existe une ER telle que
des caractères a et b.
L = L(ER).
vL’ER (a+b)(a+b) dénote le langage {aa, ab, ba, bb}, soit le langage
de toutes les chaînes de longueur 2 sur l’alphabet S. v A et B, deux ER, sont équivalentes si leurs deux langages
vL’ER a* dénote le langage des chaînes de 0,1 ou plusieurs a, soit rationnels sont équivalents : L(A) = L(B).
{e,a ,aa ,aaa ,…}.
v Pour montrer que deux langages rationnels sont
équivalents il faut prouver que L1 Í L2 et que L2 Í L1
Remarque : Il est à noter que e représente l’élément vide.

ER - Langage ER
Soit S un alphabet. Une expression régulière ER sur S est vCommutativité de l’union (mais pas
de la concaténation)
vAutres propriétés
v w0 = e
une formule qui définit un langage L(ER) sur S, de la manière v a b <> b a v w* = È{i=0..¥} wi = w0 | È{i=1..¥} wi = e | È{i=1..¥} wi = e | w+
suivante : v a|b=b|a v |w1.w2| = |w1| + |w2|
vassociativité a | Æ = Æ | a = a (élément neutre par rapport à
vSi e est une ER qui définit le langage L(e) ou {e}
v

v a (bg) = (ab) g l’union)

a | (b|g) = (a | b) | g v (Æ a) = (a Æ) = Æ (Æ est l’élément absorbant pour la

vSi aÎ S, alors a est une ER qui définit langage L(a) ou {a}
v
concaténation)
vdistributivité v (e a) = (a e) = a (e est l’élément neutre pour la
v a (b | g) = ab | ag concaténation)
(a | a) = a
vÉcritures
v

v Soient a et b deux ER, définissant les langages L(a) et L(b) : va|b=a+b

v Æ* = e (Æ^0 = e comme 0^0 = 1)
v e | aa * = e | a+ = a* (analogie 0 ~ Æ et 1 ~ e) par
v a* est une ER définissant le langage (L(a))* v Fermeture positive : l’écriture a+ = a a*
(répétition un nombre de fois au moins égal à
rapport à la concaténation et la multiplication
v ab est une ER définissant le langage L(a)L(b) 1)

v (a+b) est une ER définissant le langage L(a)ÈL(b)

Exercices Solution
vEcrire les expression régulières pour la langages 1. L1= {ab,ba,aaa,aab,bba,…}
suivants avec l’alphabet {a,b} Ø ER1=(a+b)(a+b)(a+b)*

1. Langage accepte les mots de tailles au moins 2 2. L2={e,a,b,aa,ab,ba,bb}

Ø ER2=(e+a+b)(e+a+b)
2. Langage accepte les mots de taille 2 au maximum

Langage régulier: Lemme de l’étoile Langage régulier: Lemme de l’étoile

ØSi un langage L sur un alphabet S (L Í S *) est vQuelque soit le mot |u| >= n,
régulier, si vil existe un sous mot qui se répète.
Ø$ n Î IN* (qui dépend de L) tel que vEt le schéma de répétition fg* doit être commun à tous
Ø" u Î L avec |u| ³ n, les mots du langage à partir d’une taille donnée n (n+1
qui est par la même occasion le nombre d’états qui
Øil existe une décomposition de u en trois parties
reconnaît le mot fg)
u = fgh telle que :
Øg¹e vAttention, la décomposition doit toujours trouver un
Ø |fg| £ n
sous mot g (en boucle) non loin du début du mot
|fg|<=n et ce quelque soit la taille du mot |u| >= n !!
Ø " k ³ 0, fgkh Î L
 Langage irrégulier
Langage régulier: Lemme de l’étoile Exemple
vLe lemme de l’étoile ne permet pas de démontrer qu’un vMontrer que le langage {anbp : n < p} est
langage est régulier (car il n y a pas d’équivalence entre le
fait de permettre une décomposition et la régularité du irrégulier:
langage) vPrenons un entier N suffisamment grand.
vLe lemme de l'étoile est souvent utilisé pour démontrer vPour tout mot z du langage tel que |z|≥N,
qu'un langage donné est irrégulier (par absurde)
vil existe u, v, w de A* tels que z=uvw, |v|>0,
vLe lemme de l’étoile ne permet pas de démontrer pour
tous les langages irréguliers qu’ils sont irréguliers (car des
|uv|≤N alors, normalement, pour tout entier i le
langages sont irréguliers pourtant ils permettent une mot uviw est dans {anbp : n < p}
décomposition)
vaibj i³j

Langage irrégulier Langage irrégulier

Exemple Exemple
vMontrer que le langage {anbp : n < p} est irrégulier: vApplication
vPrenons le mot z=aNbN+k avec k≥1 v Cas n=5 et p= 6, n<p
vSi z=uvw alors u=ap, v=aq avec q>0 et w=aN-(p+q)bN+k vLe mot : Z = aaaaabbbbbb
vPrennons : U=a, V=aaaa, W=bbbbbb, i=2, k=1
vDonc z = ap aq aN-(p+q)bN+k vZ=UV2W=aaaaaaaaabbbbbb
vuviw = ap (aq)i aN-(p+q)bN+k = aN (aq)i-1 bN+k = aN+q(i-1) bN+k
vDans ce cas n=9 et p=6 à n>p,
vOr pour tout i > 1+k/q vMot n’appartient pas au langage
vuviw n'est plus dans {anbp: n < p}
vcar alors N+(i-1)q > N+k ! v{anbp : n < p} est irrégulière
vDonc il ne vérifie pas le lemme de l'étoile et donc il n'est pas régulier !
 Automate à états finis
Définition
nUn automate à états finis : est un graphe où les états sont les
nœuds du graphe et les arcs représentent la fonction de
transition.

Automate à états finis

v Un automate est constitué d’un ensemble fini S d’états, d’un
alphabet fini S de symboles d’entrée et d’une fonction d de
transition qui pour chaque symbole de S permet d’atteindre un
état Î S.

v Les automates à états finis re-connaisseurs sont des

automates qui répondent "oui" ou "non" à propos de chaque
chaîne d’entrée possible.

Automate à états finis Automate à états finis Déterministe (DFA) et

Définition Non déterministe (NFA)
Soit l’alphabet S = {a, b}, et l’ER = une suite illimité de “ba”, ER=ba(ba)*
v Un automate d’états finis A est défini comme un 5-uplet
A = <S, S, d, s0, F > où :
ü S est un ensemble d'états, b a
ü S est un alphabet (un ensemble de caractères), b a b a
ü d : S ´ S ® S est la fonction de transition de l'automate,
ü s0 est l'état initial de l'automate,
vLes 2 automates peuvent générer le langage L(ER) de ER=ba(ba)*.
ü F Í S est l'ensemble des états finaux de l'automate
v Le nombre de séquences que l’automate accepte ou génère est infini, du
fait de la présence d’une boucle.
v L’ensemble des mots pouvant être acceptés par un vL’état re-connaisseur indique que l’automate peut s’arrêter, mais pas
nécessairement qu’il doit s’arrêter.
automate A est appelé le langage reconnu par A, noté L(A).
 Automate à états finis Non Déterministe
Automate à états finis Déterministe (DFA) (NFA)
v L’automate est dit déterministe (DFA) si Tous les arcs partants d’un v L’automate est dit NON-déterministe (NFA) si Certains nœuds
même nœud correspondent à des caractères différents. peuvent avoir plusieurs arcs sortants portant les mêmes
b caractères. Ici à partir du point central, 2 transitions portent
l’étiquette "a". a
b a
b a
v Soit A l’automate déterministe précédent et a un mot du
langage reconnu par A, L(A) s’écrit : vIl possède une Fonc-on de transi-on étendue δ : S × Σ ∪ {ε} →℘(S)
L(A) = {a Îå* | d(s, a) à f, f Î F} vIl existe plusieurs séquences de transferts différentes permeBant
d’obtenir a en partant de s pour arriver à f.
vIl existe une et seule séquence de transfert permettant vIl peut y a voir des transi-ons, appelées (ε-transi-ons), qui ne
d’obtenir a en partant de s pour arriver à f. correspondent à une aucune reconnaissance de caractères.

Exemple NFA
avec ε-transitions Exercices
0,1, …, 9 0,1, …, 9
vAvec l’alphabet {0,1}
e ,+,- . 0,1, …, 9 e
s0 s1 s2 s3 s5 1. Construire un DFA qui accepte les mots de
0,1, …, 9 s4 . taille 2
2. Construire un DFA qui ne contient pas le mot
e
δ S +,- . 0,1,… ,9 0011
Æ Æ
s0 {s1} {s1}
3. Construire un NFA qui accepte les mots qui se
Æ Æ
s1 {s2} {s1, s4}
terminent avec 1
s2 Æ Æ Æ {s3}
Æ Æ
4. Construire un NFA qui accepte les mots qui
s3 {s5} {s3}
Æ Æ Æ
contiennent 01
s4 {s3}
s5 Æ Æ Æ Æ
 Solution Solution
1. L’alphabet ∑={0,1}. Langage L={00,01,11,10} 3. Les mots qui se terminent par 1
0,1
0,1 0,1 1
s0 s1 s2 s0 s12

2. Commence par construire DFA qui accepte les mots qui contiennent 0011. Puis 4. Les mots qui contiennent 01.
inverser les états.
1 0,1 0,1 0,1
0

0 0 1 1 0 1
s0 s1 s2 s3 s0 s1 s
S23

1 0

Déterminisation de
NFA

S1
 Déterminisation d’NFA NFA (sans e-transitions )à DFA
ØDeux cas possible v Soit AN = <SN, SN, dN, sN0, FN > un automate non-
déterministe sans e-transitions (NFA), il existe un automate
déterministe (DFA) AD = <SD, SD, dD, sD0, FD > tel que L(AN ) =
Ø1er cas : l’automate non-déterministe est sans L(AD)
e-transition ü SD Í Ã(SN)
ü tous les éléments de Ã(SN) ne seront accessibles depuis l’état
initial de SD
Ø2ème cas : l’automate non-déterministe ü SD = SN
contient des e-transitions ü dD(sD Î SD, a Î SD) = Ès Î s dN(sN, a)
N D
ü sD0 = {sN0}
ü FD = {s Î SD | (s Ç FN) ¹ Æ}

NFA (sans e-transitions )à DFA NFA (sans e-transitions )à DFA

Exemple Exemple
0,1
Ø Soit l’automate NFA suivant :
0 1
0,1
NFA AN s0 s1 s2
0 1
s0 s1 s2 1

ØL’ensemble des états : Q = {S0,S1,S2}

DFA AD 1 0

ØL’alphabet : Σ = {0,1} δ 0 1 1
0
δ 0 1 SD0={S0} {S0 , S1} {S0} s0 {S0 , S1} {S0 , S2}
ØL’état initial est {S0} S0 {S0 , S1} {S0} {S0 , S1} {S0 , S1} {S0 , S2}
ØLes transitions sont : {S0 , S1} {S0 , S1} {S0 , S2} FD={S0 , S2} {S0 , S1} {S0}
{S0 , S2} {S0 , S1} {S0} 0

L(AN ) = L(AD) = {w=(0|1)*01}

NFA (sans e-transitions )à DFA
Exercice NFA (avec e-transitions )à DFA
1. Transformer NFA défini par NFA1={{A,B,C} , (a,b) , δ , A , {C}}, δ Dans le cas général, il faut prendre en considération les ε-transition:
donnée pas le tableau suivant:
ü Comme dans le cas simple sans ε-transition Qʹ = 2Q
ü L’alphabet n’est pas modifié : Σʹ = Σ
ü On ferme par ε : δʹ(s,a) = E(δ(s,a))
δ a b
A {A , B} {C} ü Il y a plus d’états initiaux q0ʹ = E(q0)
B {A} {B} ü L’ensemble des états finals est le même que dans le cas simple sans ε-
C ø {A , B} transition Fʹ = {S | S ∩ F ¹ Æ }

s’’’Î e-fermeture(s’’)
s’ Î e-fermeture(s) a s’’ e*
s e*

NFA (avec e-transitions )à DFA

NFA (avec e-transitions )à DFA Exemple
0,1, …, 9 0,1, …, 9
On définit la fonction ε-fermeture : S →℘(S) comme suit:
v Réflexivité : s Î e-fermeture(s) s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5
e-transition directe : Si s1Î d(s,e) alors s1 Î e-fermeture(s)
v

v Transitivité : Si s1 Î e-fermeture(s) Ù s2 Î e-fermeture(s1) alors s2 Î e-fermeture(s)

0,1, …, 9 s4 .
Calcul de la fermeture de tous les états.
v fermeture est une relation de quasi-équivalence car sans symétrie du fait que +,-
δD SE e-fermeture . 0,1,…,9
l’automate est un graphe orienté
{S0} SD0={S0, S1} {S1} {S2} {S1, S4}
v On peut définit par extension e-fermeture : Ã(S) ®Ã(S) telle que e-
{S1} {S1} Æ {S2} {S1, S4}
fermeture(S’ Í S) = Ès’ Î S’ e-fermeture(s’)
{S2} {S2} Æ Æ {S3}
s’ Î e-femeture(s)
s e* {S3} FD0={S3,S5} Æ Æ {S3}
{S4} {S4} Æ {S3} Æ
v e-fermeture(s) regroupe tous les états accessibles depuis s sur des chemins
constitués seulement de e-transitions {S5} {S5} Æ Æ Æ
 NFA (avec e-transitions )à DFA NFA (avec e-transitions )à DFA
Exemple Exemple
0,1, …, 9 0,1, …, 9 0,1, …, 9 0,1, …, 9

s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5 s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5
0,1, …, 9 s4 . 0,1, …, 9 s4 .
On doit effectuer un post-processing : calcul de la fermeture après les calculs des images δD SE e-fermeture +,- e-fermeture . e- 0,1,…,9 e-fermeture
δD SE e-fermeture +,- e-fermeture . e-fermeture 0,1,…,9 e-fermeture fermeture
{S0} SD0={S0, S1} {S1} {S1} {S2} {S2} {S1, S4} {S1, S4} {S0} SD0={S0, S1} {S1} {S1} {S2} {S2} {S1, S4} {S1, S4}
{S1} {S1} Æ Æ {S2} {S2} {S1, S4} {S1, S4} {S1} {S1} Æ Æ {S2} {S2} {S1, S4} {S1, S4}
{S2} {S2} Æ Æ Æ Æ {S3} {S3,S5} {S2} {S2} Æ Æ Æ Æ {S3} {S3,S5}
{S3} FD0={S3,S5} Æ Æ Æ Æ {S3} {S3,S5} {S3} FD0={S3,S5} Æ Æ Æ Æ {S3} {S3,S5}
{S4} {S4} Æ Æ {S3} {S3,S5} Æ Æ {S4} {S4} Æ Æ {S3} {S3,S5} Æ Æ
{S5} {S5} Æ Æ Æ Æ Æ Æ {S5} {S5} Æ Æ Æ Æ Æ Æ
On remarque qu’il y a des état fermetures accessibles dont on n’a pas calculé les images {S1, S4} Æ Æ {S2,S3} {S2, S3,S5} {S1, S4} {S1, S4}
Solution ==> on réinjecte ces nouvelles états {S1, S4} dans le calcul

NFA (avec e-transitions )à DFA NFA (avec e-transitions )à DFA

Exemple Exemple
0,1, …, 9 0,1, …, 9 0,1, …, 9 0,1, …, 9

s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5 s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5
0,1, …, 9 s4 . 0,1, …, 9 s4 .
δD SE e-fermeture +,- e-fermeture . e-fermeture 0,1,…,9 e-fermeture
On élimine les états inaccessibles à partir de e-fermeture
{S0} SD0={S0, S1} {S1} {S1} {S2} {S2} {S1, S4} {S1, S4}
δD SE e-fermeture +,- e-fermeture . e-fermeture 0,1,…,9 e-fermeture
{S1} {S1} Æ Æ {S2} {S2} {S1, S4} {S1, S4}
{S0} SD0={S0, S1} {S1} {S1} {S2} {S2} {S1, S4} {S1, S4}
{S2} {S2} Æ Æ Æ Æ {S3} {S3,S5}
{S1} {S1} Æ Æ {S2} {S2} {S1, S4} {S1, S4}
{S3} FD0={S3,S5} Æ Æ Æ Æ {S3} {S3,S5}
{S2} {S2} Æ Æ Æ Æ {S3} {S3,S5}
{S4} {S4} Æ Æ {S3} {S3,S5} Æ Æ
{S3} FD0={S3,S5} Æ Æ Æ Æ {S3} {S3,S5}
{S5} {S5} Æ Æ Æ Æ Æ Æ
{S1, S4} Æ Æ {S2,S3} {S2, S3,S5} {S1, S4} {S1, S4}
{S1, S4} Æ Æ {S2,S3} {S2, S3,S5} {S1, S4} {S1, S4}
FD0={S2, S3,S5} Æ Æ Æ Æ {S3} {S3,S5}
FD0={S2, S3,S5} Æ Æ Æ Æ {S3} {S3,S5}
 NFA (avec e-transitions )à DFA NFA (avec e-transitions )à DFA
Exemple Exemple
0,1, …, 9 0,1, …, 9 0,1, …, 9 0,1, …, 9

s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5 s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5
0,1, …, 9 s4 . 0,1, …, 9 s4 .
ü Style plus compact de
représentation du résultat : Au lieu
δD SE e-fermeture +,- e-fermeture . e-fermeture 0,1,…,9 e-fermeture δD SE e-fermeture +,- . 0,1,…,9 de faire en une ligne e-f (d(e-f(s), l))
et d’injecter ce résultat final dans
{S0} SD0={S0, S1} {S1} {S1} {S2} {S2} {S1, S4} {S1, S4} {S0} SD0={S0, S1} {S1} {S2} {S1, S4} une nouvelle ligne
{S1} {S1} Æ Æ {S2} {S2} {S1, S4} {S1, S4} {S1} {S1} Æ {S2} {S1, S4}
ü On fait sur la première ligne d(e-
{S2} {S2} Æ Æ Æ Æ {S3} {S3,S5} {S2} {S2} Æ Æ {S3, S5} f(s), l)=s*, puis après injection de
s* dans la deuxième ligne on
{S3} FD1={S3,S5} Æ Æ Æ Æ {S3} {S3,S5} {S1, S4} {S1, S4} Æ {S2,S3, S5} {S1, S4} calcule d(e-f(s*), l)=s*
{S1, S4} Æ Æ {S2,S3} {S2, S3,S5} {S1, S4} {S1, S4} {S3, S5} FD1={S3, S5} Æ Æ {S3, S5}
ü e-f : epsilon-fermeture
FD2={S2, S3, S5} Æ Æ Æ Æ {S3} {S3,S5} {S2, S3} FD2={S2, S3, S5} Æ Æ {S3, S5}

NFA (avec e-transitions )à DFA NFA (avec e-transitions )à DFA

Exemple Exercice
0,1, …, 9 0,1, …, 9
ü Trouver DFA équivalent
e-NFA AE
s0
e ,+,-
s1
. s2
0,1, …, 9
s3
e
s5
0,1, …, 9 s4 . 0 1 0,1

e e
. 0,1, …, 9 s0 s1 s2
DFA AD .
+,- {S1} 0,1, …, 9
{S2} {S3 , S5}
{S0, S1}

0,1, …, 9
. 0,1, …, 9
0,1, …, 9 {S1, S4} {S2, S3 , S5}

0,1, …, 9
L(AE) = L(AD) = langage des nombres réels
NFA (avec e-transitions )à DFA
Solution
0 1 0,1

e e
s0 s1 s2

δD S e-fermeture 0 1 ER à NFA
Algorithme de Thompson
{S0} {S0, S1 , S2} {S0, S1 , S2} {S1 , S2}

{S1 , S2} {S1 , S2} {S2} {S1 , S2}

{S2} {S2} {S2} {S2}
0 1 0,1

1 0
s0 s1 s2 s1 s2 s2

ERà NFA ERà NFA

Algorithme de Thompson Algorithme de Thompson
v Il existe de nombreuses façons de construire un tel
automate, celle que nous donnons ci- dessous est la e a b
construction de Thompson « pure » qui présente quelques
propriétés simples : NFA e NFA a NFA b
v Un unique état initial q0 sans transition entrante
v Un unique état final qF sans transition sortante
v Exactement deux fois plus d’états que de symboles dans l’expression a e b
rationnelle (sans compter les parenthèses ni la concaténation,
implicite).
NFA ab
v Cette dernière propriété donne un moyen simple de
contrôler le résultat en contrepartie d’automates parfois L’algorithme de Thompson est un algorithme sans destruction (utilise les ajouts des
plus lourds que nécessaire. transitions et des états, sans en supprimer)
ERà NFA ERà NFA
Algorithme de Thompson Algorithme de Thompson
Exemple Exercice
a
e S2 S3 e
S1 Sf
NFA d’ER par Thompson (a+b)*b
e S3
b S4 e
e
NFA (a+b) S1
e
S2
a S4
e
Sf

e
NFA a*

ERà NFA
Algorithme de Thompson
Solution

a e
e
e e e e b

e b e
(a+b)* b
S2
 DFAàER
équations linéaires
vSoitA = <S, S, d, s0, F > un automate fini.
vSE(A) est le système d’équations de A

DFAà ER vXsÎS = åd(s,a) =s’ aXs’ + (si sÎF alors e sinon Æ)

Equations linéaires a b
b X1 = aX1 + bX2 + e
1 2 X2 = bX2 + (a + c) X3
c a,c X3 = cX1
3

DFAàER DFAàER
équations linéaires équations linéaires
v Théorème : v Etape 0 a b
Soit A un automate et (Ls ÎS) la plus petite solution associée à Xs
v
dans SE(A), alors L(A) = Ls0 v X1 = aX1 + bX2 + e b
1 2
v X2 = bX2 + (a + c) X3
v Lemme v X3 = cX1
c a,c
3
v Soient A, B Í S* des langages.
v Le langage A*B est une solution de l’équation v Etape 1
v X = AX + B (équation du point fixe X = f(X))
v X1 = aX1 + bX2 + e
v Lemme d’Arden v X2 = bX2 + (a + c) cX1 (X3 remplacée par sa valeur)
v Si e Ï A alors A*B est la solution unique de X = AX + B v X3 = cX1
 a b
DFAàER b DFAàER
équations linéaires 1 2
équations linéaires
v Etape 1
c a,c v Etape 3
3
v X1 = aX1 + bX2 + e v X1 = aX1 + b b*(a + c)cX1 + e (X2 remplacée par sa valeur)
v X2 = b*(a + c)cX1
v X2 = bX2 + (a + c) cX1 (X3 remplacée par sa valeur)
v X3 = cX1
v X3 = cX1
v Etape 4
v Etape 2
v X1 = (a + b b*(a + c) c)X1 + e (factorisation car distributivité)
v X1 = aX1 + bX2 + e
v X2 = b*(a + c)cX1
v X2 = b*(a + c)cX1 (Résolution de X2 par Application du lemme où
A = b et B = (a + c)cX1) v X3 = cX1
v X3 = cX1
v L(A) = X1 (du fait que X1 est associé à l’état initial de l’automate)
v Etape 3
v X1 = aX1 + b b*(a + c)cX1 + e (X2 remplacée par sa valeur) v L(A) = (a + b b*(a + c) c)*. e Lemme d’Adren:
v X2 = b*(a + c)cX1 Eq: X = AX + B à Solution A*B
v = (a + b b*(a + c) c)*
v X3 = cX1
v = (a + b+(a + c) c)*

DFAàER
équations linéaires
Exercice
Trouvez l’ER de l’automate suivant:

a DFAà ER
1 2
Base de graphe
a b a
b
3 4 a,b
b
DFAà ER DFAà ER
Base de graphe Base de graphe
vR0i,j={a Î S | d(i, a) = j} È {e si i = j}
vSoit A = <S, S, d, s0, F > un automate déterministe
v" kÎ {1,..,n}, Rki,j = Rk-1i,j + Rk-1i,k .(Rk-1k,k)*. Rk-1k,j
vSoit {1, 2, …, n} une image de S dans IN*
(Rk-1k,k)*
vOn définit Rki,j comme l’expression régulière
décrivant le langage des mots w reconnus par un k
Rk-1k,j
chemin de l’état i à l’état j dans A ne contenant pas Rk-1i,k

d’état intermédiaire supérieur strictement à k. j

i
vL(Rki,j)={w =u1u2…u|w|Î S* | d(i, u1) £ k Ù d(d(i, u1), u2) £ k Ù Rk-1i,j
d(d(d(i, u1), u2), u3) Ù d(d(…d(i, u1), ….u|w|-1), u|w|)=j £ k }
vER(A) = expression régulière définissant les mots reconnus par les
chemins allant de l’état initial vers l’état final et pouvant passer
par les |S| états de l’automate A
v ER(A) = R|S|S ,F
0

DFAà ER DFAà ER 1 0,1

Base de graphe Base de graphe 0
Exemple Exemple 1 2

vk = 0
Trouvez l’ER reconnu par l’automate suivant: v R01,1 = 1 + e Î S | d(i, a) = j} È {e si i = j}
vR0i,j={a
v R01,2 = 0 v" kÎ {1,..,n}, Rki,j = Rk-1i,j + Rk-1i,k .(Rk-1k,k)*. Rk-1k,j
v R02,1 = Æ
1 0,1 vk
v R02,2 = 0+1+e
= 1, R1i,j = R0i,j + R0i,1 .(R01,1)*. R01,j
0 v R11,1 = (1 + e) + (1 + e).(1 + e)*.(1 + e) = (1 + e).(e +(1 + e)+) =(1 + e).(1 + e)* = (1 + e)+
1 2 v R11,2 = 0 + (1 + e).(1 + e)*.0 = 0 + (1 + e)+.0 = (1 + e)*.0
v R12,1 = Æ + Æ .(1 + e)*.(1 + e) = Æ
v R12,2 = (0 + 1 + e) + Æ .(1 + e)*.0 = (0 + 1 + e)
vk = 2,
v R21,2 = R11,2 + R11,2 (R12,2)* R12,2

Ø Cela revient à calculer R|S|S0,F =R21,2 v = ((1 + e)*0) + ((1 + e)*0) (0 + 1 + e)*(0 + 1 + e)
v = ((1 + e)*0) (e + ((0 + 1 + e)*(0 + 1 + e)))
v = ((1 + e)*0) (0 + 1 + e)*
v = (1*0) (0 + 1)*
v R21,2 = 1* 0 (0 + 1)*
 ERàDFA
Algorithme de Glushkov

S3

ERàDFA ERàDFA
Algorithme de Glushkov Algorithme de Glushkov
Entrée : Soit E une expression régulière
vL'algorithme construit un automate acceptant
v
v On transforme E en E’ en indiçant toute lettre de 1 .. n (indice = état potentiel)
l'ensemble des mots décrit par une expression v On ajoute l’état 0 au début de E’

régulière. v On place une transition de 0 vers i (d(0, lj) ¬ i)

v ssi la lettre li peut être la première lettre d’un mot du langage L(E’)
vLes grandes étapes de l'algorithme partant d'une v déterminisation systématique (si j¹k et d(0, l) = {j,k}, alors l’état composite {j,k} regroupera les états atomiques j et k)

expression rationnelle E sont les suivantes. v On place une transition de i vers j étiquetée par la lettre lj (d(i,lj)¬j)
v ssi la lettre lj peut suivre la lettre li dans un mot du langage L(E’)
vTransformer l'expression E en une nouvelle expression E' v déterminisation systématique : si j¹k et d(i, l) = {j,k}, alors l’état composite {j,k} regroupera les états atomiques j et k

où chaque lettre apparaît au plus une fois dans E'. v L’état i (i > 0) est final
vConstruire un automate A' acceptant l'ensemble des v
v ssi li peut être la dernière lettre d’un mot du langage L(E’)
L’état 0 est final
mots décrit par E' v ssi e est dans le langage L(E’)
v Sortie : A = < S, S, d, s0, F >
ERàDFA ERàDFA
Algorithme de Glushkov Algorithme de Glushkov
Exemple Exercice
Entrée : Soit E = (a+e) (ba)* (b+e) une expression régulière
vCalculer les automates des ER
v
v E’ ¬ E Indicée
v E’ ¬ (a1+e) (b2a3)* (b4+e)
v
v
E’ ¬ 0E’
E’ ¬ 0(a1+e) (b2a3)* (b4+e)
1. (a+b)*a
v Premières lettres possibles et transitions initiales
v d(0, a) ¬ 1; d(0, b) ¬ {2,4} (* Déterminisation systématique par regroupement des états)

d(i,lj)¬j ssi li peut être suivie de lj

(a+b)*a(b+c)*
v
v

v
d(1, b) ¬ {2,4} (*)
d({2,4}, a) ¬ 3 (*)
a 2.
0 1
v d(3, b) ¬ {2,4} (*)

v Dernières lettres et transitions finales

b b
v F ¬ {1, 3, {2,4}} l4 peut être à la fin, donc {2,4} est final !
2,4
v L’état initial est-il final ?
F ¬ F È {0} a
b
v

v Sortie : A = < S={0,1,{2,4},3}, S={a,b}, d, s0={0}, F >

ERàDFA
Algorithme de Glushkov
Solution - 1
vCommence par numéroté les symboles
Ø0(a1+b2)*a3

δ a b
Minimisation de ER
a a 0
2
{1 , 3}
{1 , 3}
{2}
{2}
Résiduel à gauche
a
0 1,3
1
{1 , 3} {1 , 3} {2}

b
b 2

b
Minimisation de ER Minimisation de ER
Résiduel à gauche Résiduel à gauche
vSoit L un langage surun alphabet S, on appelle L
résiduel à gauche (suffixe) de L par rapport à un Les résiduels, ce
mot u ÎS * l’ensemble des mots vÎS * tels que uv sont tous les V qui
Î L (on note u-1L) restent à droite
vu-1L = {v ÎS *, uv Î L}
U V
vPropriétés:
vL’ensemble des résiduels à gauche (suffixes) de L v{ε}-1L = L
est l’union pour tout uÎS * des u-1L v∅-1L= ∅
vR(L) = Èu ÎS * u-1L
v({u v})-1L= {v}-1 ({u}-1L)

Minimisation de ER
Minimisation de ER Résiduel à gauche
Résiduel à gauche Exemple
vSoit A= <S, S, d, s0, F> un automate, on appelle le langage associé à un vSoit E = 1* 0 ( 0 + 1)
état sÎ S (et on note Ls(A)) le langage reconnu par l’automate dont s est vCalculant R(L(E))
l’état initial et F l’ensemble des états finaux Ls(A)={w ÎS * / d*(s,w) Î F} v 0-1 (L) = (0 + 1) suffixe de L pour 0
(ensemble des suffixes de L reconnus à partir de l’état s) v 1-1 (L) = 1* 0 (0 + 1) = (L) suffixe de L pour 1 (point fixe)

v 0-1 (0-1L) = 0-1(0 + 1) = (e) suffixe d’ordre 2 de L pour 0

vProposition : L’ensemble des résiduels à gauche (suffixes) de L est v 1-1 (0-1L) = 1-1(0 + 1) = (e) suffixe d’ordre 2 de L pour 1
l’union des langages associés aux états de l’automate minimal le
reconnaissant v 0-1 (0-1 (0-1L)) = 0-1 (1-1 (0-1L)) = 0-1(e) = (Æ) suffixe d’ordre 3 de L pour 0
v R(L) = ÈsÎ S Ls(A) v 1-1 (0-1 (0-1L)) = 1-1 (1-1 (0-1L)) = 1-1(e) = (Æ) suffixe d’ordre 3 de L pour 1

v 0-1 (Æ) = (Æ) …..

vConséquence : donc calculer l’automate minimal reconnaissant une ER v 1-1 (Æ) = (Æ) …..
(ensemble des langages associés à ces états) revient à calculer R(L(ER))
Minimisation de ER Minimisation de ER
Résiduel à gauche Résiduel à gauche
Exemple Exercice -1-
vE = 1* 0 ( 0 + 1)
0 1 Trouver l’automate ER=(0+1)*01(0+1)*
v 0-1 (L) = (0 + 1) L 0+1 L
v 1-1 (L) = (L) 0+1 e e
e Æ Æ
v 0-1 ((0 + 1) ) = (e)
Æ Æ Æ
v 1-1 ((0 + 1)) = (e)

v 0-1 (e) = (Æ)

v 1-1 (e) = (Æ) 1 0,1

v 0-1 (Æ) = (Æ) 0 0,1 0,1

v 1-1 (Æ) = (Æ)
L 0+1 se2 Æ

Minimisation de ER Minimisation de ER
Résiduel à gauche Résiduel à gauche
Solution -1- Exercice -2-
vSoit E=(0+1)*01(0+1)* 0 1 vCalculer les automates minimal ER
v0-1 (L) = L+1(0+1)*
v1-1 (L) = L
L 0-1 (L) L 1. (a+b)*a
0-1 (L) 0-1 (L) Σ*
v0-1 (0-1 (L) ) = 0-1 (L) Σ* Σ* Σ*
v1-1 (0-1 (L) ) = Σ* v Comparer les deux automates (Glushkov et
RàG)
v0-1 (Σ* ) = Σ*
v1-1 (Σ* ) = Σ* 1 0 0,1

0 1
L 0-1 (L) s
Σ*2
Minimisation de ER
Résiduel à gauche
Solution -2-
vSoit E=(a+b)*a
va-1 (L) = L+ e
vb-1 (L) = L

Glushkov
va-1 (a-1 (L) ) = L+ e = a-1 (L)
vb-1 (a-1 (L) ) = L a a
RàG a 0
a 1,3
1
b

a b
L a-1 (L)
b
S4
2

b
b

Minimisation d’un DFA

Par séparation des états
v Deux états p,q de A sont dits équivalents (non-
distinguables) p » q ssi " wÎS*, d(p,w) Î F Û d(q,w) Î F
v w = e, si p Î F Ù q Ï F alors p et q sont distinguables

Minimisation d’un DFA (non équivalents)

v w ¹ e, (d(p,w)=r et d(q,w)=s) Ù (r et s sont distinguables) alors
Par séparation des états p et q sont distinguables

vOn note [p Î S] la classe d’équivalence de p (l’ensemble

des états q qui lui sont équivalents)
 Minimisation d’un DFA
Minimisation d’un DFA Par séparation des états
Par séparation des états Exemple
vÉtape 0 :
v p, q Î S, p »0 q ssi
0 1
v (p Î F Ù q Î F) Ú (p Ï F Ù q Ï F) 0 1
0 1 0 A B F
vÉtape i :
A B C D B G C
v " i>0, p »i q ssi 0 1 C A C
v p »i-1 q 1 D C G
0
v Ù " lÎS, d(p,l) »i-1 d(q,l) 1 1 0 E H F
E F G H F C G
vÉtape finale (arrêt des itérations) : G G E
0
v »i = »i-1
1 H G C

0
vNB. Pour vérifier qu’un automate est minimal, il faut au moins deux
itérations »0 et »1. Si »1 = »0, l’automate est minimal

0 1
Minimisation d’un DFA Minimisation d’un DFA A
B
B
G
F
C
Par séparation des états Par séparation des états C A C
Exemple Exemple D C G
E H F
0 Equivalent: {A,B,D,E,F,G,H} {C} F C G
Transition
G G E
0 1 1 Equivalent: {A,E,G} {B,H}, {D,F} {C}
H G C
A B F
0 Equivalent: {A,B,D,E,F,G,H} {C} 2 Equivalent: {A, E} {B,H} {C} {D,F} {G}
B G C
C A C
1 Equivalent: {A,E,G} {B,H}, {D,F} {C}
D C G
3 Equivalent: {A, E} {B,H} {C} {D,F} {G}
Amin
2 Equivalent: {A, E} {B,H} {C} {D,F} {G} 0
E H F 1
3 Equivalent: {A, E} {B,H} {C} {D,F} {G}
F C G
1
G G E 0
A
B,H C
H G C
0 0
A,E 0
1 1
G D,F
1
Minimisation d’un DFA Minimisation d’un DFA
Par séparation des états Par séparation des états
Propriété Propriété
v Pour tout chemin. dans vL’algorithmede minimisation s’arrête
l’automate A, il existe un chemin
dans l’automate Amin, où [sn] est un état final de Amin. car le nombre d’itérations est fini
Par conséquent, tout mot a1a2 . . . an accepté par A est vNombre d’itérations de l’algorithme
aussi accepté par Amin
vAu minimum : 2
vRéciproquement, à tout chemin vAu Maximum : |S|
correspond un chemin où s’i
appartient à [si]. Donc, tout mot a1a2 . . . An accepté par
Amin est aussi accepté par A.

Minimisation d’un DFA Minimisation d’un DFA

Par séparation des états Par séparation des états
Exercice Solution 0

ü Minimiser l’automate suivant : 0 1 1 0

A B C A C E
0
B A D 1
0 0 1
1 0 C E F
0
A C E D E F
1 E E F B
1
D
1
F
0 0 1 F F F
0
0,1
B D F 0 Equivalent: {A , B , F} {C , D, E}
1 1
0 0 0,1
0,1 1 Equivalent: {A , B} {F} {C , D, E}
1 1
2 Equivalent: {A , B} {F} {C , D, E} A,B C,D,E F
 Minimisation d’un DFA Minimisation d’un DFA
Par remplissage de tableau 0
Par remplissage de tableau
Méthode Myhill-Nerode A
Méthode Myhill-Nerode
A
1 0 Etape 3
B Etape 1 A C E B
C X X
0 0 1
1
C X X (A,B) et (C,D,E)
D X X 0 D X X
E X X E X X
B D F
1 1 X X X
F X X X F
0
A A
A B C D E F 0,1 A B C D E F
B Etape 2 B Etape 3
1 0 0 0 0,1
A C E
C X X C X X
D X X D X X 1
0 0 1 1 1
0 A,B C,D,E F
E X X E X X
F X X X F X X X B
1
D
1
F

A B C D E F A B C D E F
DFA minimisé
Combiner les états non cochés 0,1

Minimisation d’un DFA Minimisation d’un DFA

Par remplissage de tableau Par remplissage de tableau
Exercice Solution
üMinimiser l’automate suivant par remplissage de table: A A A A
B B B ✻ B ✻
0 0 C C C ✻ C ✻
D D D D
0 B D
1 E X X X X E X X X X E X X X X E X X X X
0 1
A B C D E A B C D E A B C D E A B C D E
0
A
Etape 1 0 0 Etape 2 Etape 3 Etape 4
1 C E 0 0
1 0 B
1 D

0 1 B D
1 0 1 Fusion de A et C 0 1
A

A,C 0 1
1 C E
1
1 1 E
S5