Theorie de Langages Et Automates-Resumé
Theorie de Langages Et Automates-Resumé
Theorie de Langages Et Automates-Resumé
Departement de mathematiques
Theorie des automates
et langages formels
1
a
c
b
2
a
d
c
b
3
a,c,d
b
4
b
c
a
5
d
c
a
6
b,c,d
a
7
a,b
c
8
d
c
9
a,b,c,d
a,b
b
d
d
d
Annee academique 20092010
Michel Rigo
Table des mati`eres
Chapitre I. Mots et langages 1
1. Premi`eres denitions 1
2. Langages 10
3. Expressions reguli`eres et langages associes 15
4. Exercices 22
Chapitre II. Automates 27
1. Automates nis deterministes 27
2. Automates non deterministes 29
3. Stabilite des langages acceptes par automate 39
4. Produit dautomates 43
5. Exercices 46
Chapitre III. Langages reguliers et automates 51
1. Des expressions aux automates 51
2. Des automates aux expressions reguli`eres 54
3. Stabilite de la regularite 57
4. Crit`ere de non-regularite 58
5. Exercices 61
Chapitre IV. Automate minimal 63
1. Introduction 63
2. Congruence syntaxique 64
3. Automate minimal 66
4. Construction de lautomate minimal 72
5. Applications 77
6. Exercices 81
Chapitre V. Quelques complements sur les langages reguliers 85
1. Transduction 85
2. Recherche dun mot dans un texte 88
3. Fonction de complexite dun langage regulier 92
4. Monode syntaxique 99
5. Langages sans etoile 105
6. Exercices 109
Chapitre VI. Introduction aux langages algebriques 115
1. Premi`eres denitions 115
i
ii Chapitre . Table des mati`eres
2. Arbres danalyse 119
3. Une illustration de lambiguite 122
4. Grammaires et langages reguliers 126
5. A propos de la hierarchie de Chomsky 128
6. Formes normales 130
7. Lemme de la pompe 140
8. Automates ` a pile 143
9. Stabilite du caract`ere algebrique 151
10. Un theor`eme de Sch utzenberger 152
11. Exercices 155
Bibliographie 159
Liste des gures 161
Index 165
CHAPITRE I
Mots et langages
Ce premier chapitre introduit quelques concepts fondamentaux de la
theorie des langages formels et de la combinatoire sur les mots. La com-
binatoire des mots etudie les proprietes des suites de symboles. La theorie
des langages formels englobe la theorie des automates et sinteresse aux pro-
prietes mathematiques des langages qui sont des ensembles de mots. Elle
trouve notamment des applications en verication et pour la compilation.
1. Premi`eres denitions
Denition I.1.1. Un alphabet est un ensemble ni. Un alphabet sera en
general designe par une lettre grecque majuscule. Ainsi,
= a, b, c, = , , , , = 0, 1, = , , ,
sont des alphabets. Les elements dun alphabet sont appeles lettres ou sym-
boles
Exemple I.1.2. Le biologiste interesse par letude de lADN utilisera un
alphabet ` a quatre lettres A, C, G, T pour les quatre constituants des g`enes:
Adenine, Cytosine, Guanine et Thymine.
Denition I.1.3. Soit un alphabet. Un mot sur est une suite nie
(et ordonnee) de symboles. Par exemple, abbac et ba sont deux mots sur
lalphabet a, b, c. La longueur dun mot w est le nombre de symboles
constituant ce mot; on la note [w[. Ainsi,
[abbac[ = 5 et [ba[ = 2.
Lunique mot de longueur 0 est le mot correspondant ` a la suite vide. Ce
mot sappelle le mot vide et on le note . Lensemble des mots sur est
note
. Par exemple,
a, b, c
= , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, . . ..
Denition I.1.4. Si est une lettre de lalphabet , pour tout mot w =
w
1
w
k
, on denote par
[w[
= #i 1, . . . , k [ w
i
=
le nombre de lettres
i
apparaissant dans le mot w. Par exemple, [abbac[
a
=
2 et [abbac[
c
= 1.
1
2 Chapitre I. Mots et langages
Si lalphabet de cardinal n 1 est ordonne, on pourra le considerer
comme un n-uple = (
1
, . . . ,
n
). On denit alors la fonction de Parikh
:
N
n
par
(w) = ([w[
1
, . . . , [w[
n
).
Le n-uple (w) est appele vecteur de Parikh de w. Il est clair que si n > 1,
alors nest pas injectif.
Denition I.1.5. Soit w = w
1
w
= w
sont les prexes de w. Un prexe de w dierent de et de w est dit propre.
De fa con semblable,
, w
, w
1
w
, . . . , w
2
w
, w
1
w
= w
sont les suxes de w. Un suxe de w est qualie de propre sil di`ere de
et de w. Soient 1 i j . Le mot w
i
w
j
est un facteur du mot w. On
le note parfois w[i, j]. Une fois encore, on parle de facteur propre lorsque ce
dernier di`ere de w et de . Lensemble des prexes (resp. suxes, facteurs)
de w est note Pref(w) (resp. Su(w), Fac(w)).
Remarque I.1.6. On peut observer que puisque est un ensemble ni,
est denombrable
1
.
Rappelons la denition dun monode.
Denition I.1.7. Soient A un ensemble et : A A A une opera-
tion binaire interne et partout denie. Lensemble A muni de loperation
poss`ede une structure de monode si les proprietes suivantes sont satisfaites.
Loperation est associative :
x, y, z A : (x y) z = x (y z).
Il existe un neutre (unique) e A tel que
x A : x e = e x = x.
Remarque I.1.8. Un monode (A, ) qui est tel que tout element de A
poss`ede un inverse est un groupe.
Exemple I.1.9. Tout groupe est un monode; (N, +) est un monode qui
nest pas un groupe.
Protons-en pour rappeler la denition dun morphisme de monodes.
1
En eet, les elements de
, u
i
, v
i
, la concatenation de u et v, notee u.v ou simplement
uv, est le mot On utilisera
dorenavant
la notation
multiplicative.
w = w
1
w
k+
o` u
_
w
i
= u
i
, 1 i k
w
k+i
= v
i
, 1 i
.
Ainsi,
est
un monode non commutatif, i.e., il existe u, v
N
est un morphisme de monodes entre (
dans ( c)
en identiant le mot ni w
n+2
(a) =
n+1
(a)(u). De plus, la suite ([
n
(a)[)
n0
est strictement crois-
sante. Pour ces deux raisons et avec la topologie associee ` a la metrique
presentee precedemment, on peut dire que la suite (
n
(a))
n0
converge vers
un mot inni limite.
3
On rencontre notamment ce type de propriete en analyse p-adique. La topologie
associee est interessante : tout point dune boule en est le centre, deux boules ont une
intersection non vide si et seulement si lune est incluse dans lautre, tout triangle est
isoc`ele, etc.
I.1. Premi`eres denitions 5
0
(a) = a
1
(a) = abc
2
(a) = abcacb
3
(a) = abcacbabcbac
.
.
.
La demonstration du fait que le mot inni limite
tel que v = u
u et [u
u = vu = u
uu et donc on trouve u
u = uu
. Puisque [uu
[ < [uv[,
on peut appliquer lhypoth`ese de recurrence. Il existe un mot w et des
entiers p, q tels que u = w
p
et u
= w
q
. Pour conclure, on remarque que
v = u
u = w
p+q
.
un mot, avec w
i
pour tout i.
Lentier k 1 est une periode de w si
w
i
= w
i+k
, i = 1, . . . , k.
I.1. Premi`eres denitions 7
On dit aussi que w est k-periodique. Un mot 1-periodiqe est constant. Par
exemple, le mot
abbabbabba
est 3-periodique. Au vu de cette denition, un mot de longueur est p-
periodique pour tout p .
Lemme I.1.22. Soient p, q deux entiers. Si w est (p.q)-periodique avec
[w[ p.q et si le prexe de w de longueur p.q est p-periodique, alors w est
lui-meme p-periodique.
Demonstration. Cest evident.
5
N. J. Fine, H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer.
Math. Soc. 16 (1965), 109114.
6
Denir f sur {0, . . . , p + q 1} et non sur {1, . . . , p + q 1} comme cela aurait pu
sembler naturel, nous sera bien utile. Au vu de la preuve, pourquoi ?
8 Chapitre I. Mots et langages
Nous pouvons ` a present proceder ` a la preuve du theor`eme de Fine et
Wilf.
Demonstration. On peut supposer que [w[ = p +q pgcd(p, q). En fait,
si le mot w est plus long, on consid`ere son prexe v de longueur p + q
pgcd(p, q). Si lon montre que v poss`ede pgcd(p, q) comme periode, alors
gr ace au lemme I.1.22, le resultat setend ` a w tout entier car w poss`ede dej` a
p ou q comme periode.
On peut de plus supposer que d = pgcd(p, q) = 1, car sinon, en prenant
une lettre sur d dans w, on est presence de d mots de longueur k = p/d +
q/d 1
w
i
w
i+d
w
i+(k1)d
, i = 1, . . . , d
et de periodes p/d et q/d premi`eres entre elles. Au vu du lemme I.1.24,
chacun des d mots est constant et on en tire la d-periodicite de w.
et w
R
= u
R
. Si w est tel
que
w
R
= w,
alors w est un palindrome.
Denition I.1.26. Un mot ni de la forme auaua o` u u
et a est
un chevauchement (en anglais, overlap).
a u a u a
On remarque que tout chevauchement contient un carre. De meme, un cube
(i.e., mot de la forme uuu) est un chevauchement particulier.
Nous avons vu que sur un alphabet binaire, tout mot de longueur 4
contient un carre. Le fait de contenir un chevauchement est une propriete
plus forte. Cette propriete est-elle evitable sur deux lettres ?
Proposition I.1.27. Le mot de Thue-Morse, deni comme t = f
(a) o` u
f(a) = ab et f(b) = ba, est un mot inni sans chevauchement.
7
On utilise la lettre R car la terminologie anglo-saxonne fait souvent reference au mot
reversal ou reverse. Dans la litterature, on trouve parfois la notation e w.
I.1. Premi`eres denitions 9
t = abbabaabbaababbabaababbaabbabaab
La preuve de ce resultat est calquee sur celle presentee dans [21]. Pour
des applications du mot de Thue-Morse, on lira [4].
Lemme I.1.28. Soit X = ab, ba. Si x appartient ` a X
, alors axa et
bxb nappartiennent pas ` a X
.
Demonstration. On proc`ede par recurrence sur [x[. Si x = , il est clair
que aa, bb , X
, on en conclut,
par hypoth`ese de recurrence, que byb = x nappartient pas ` a X
. Ceci est
une contradiction.
.
Puisqe f est 2-uniforme (i.e., [f(a)[ = [f(b)[ = 2), [f(w)[ est pair. On
remarque que [cvcvc[ = 3 +2[v[ est impair. Par consequent, [xy[ est impair.
Montrons ` a present que [v[ est impair.
Si [x[ est pair, alors x, cvcv et cy appartiennent ` a ab, ba
.
D`es lors, si [v[ etait pair, alors cvc et v appartiendraient ` a ab, ba
.
Ceci est en contradiction avec le lemme precedent.
Si [x[ est impair, alors xc, vcvc et y appartiennent ` a ab, ba
. Si
[v[ etait pair, on aboutirait ` a la meme contradiction.
Nous pouvons ` a present conclure, en discutant une fois encore sur la
parite de [x[.
Si [x[ est pair, alors, puisque [v[ est impair, on a
f(w) = x
..
pair
c
impair
..
v
. .
pair
cv
..
pair
cy ab, ba
a, b
deni par
g :
_
_
_
a abb
b ab
c a
.
Si r un mot inni sur a, b sans chevauchement et debutant par a, alors il
existe un unique mot inni s sur a, b, c tel que g(s) = r.
Proposition I.1.31. Soit t un mot inni sur a, b sans chevauchement et
debutant par a (comme le mot de Thue-Morse). Soit s lunique mot inni
a, b, c tel que g(s) = t. Alors s est un mot inni sur trois lettres sans
carre.
Demonstration. Supposons que s contienne un carre : s = xuuy avec
u non vide, une lettre et y un mot inni. Alors g(s) contient le facteur
g(u)g(u)g() qui debute par un chevauchement car g(u) et g() debutent
par la meme lettre.
2. Langages
Nous en avons termine avec notre br`eve introduction ` a la combinatoire
des mots. Passons ` a la theorie des langages formels.
8
On remarquera que {a, ab, abb} est un code.
I.2. Langages 11
Denition I.2.1. Un langage sur est simplement un ensemble (ni ou
inni) de mots sur . En dautres termes, un langage est une partie de
.
On distingue en particulier le langage vide
9
.
Exemple I.2.2. Considerons lalphabet = a, b, c. Lensemble
a, aa, bbc, ccca, ababab
est un langage ni. Lensemble L
2a
des mots sur comprenant un nombre
pair de a est aussi un langage (inni),
L
2a
= , b, c, aa, bb, bc, cb, cc, aab, aac, aba, aca, . . . , abaacaaa, . . ..
Lensemble Pal(
) = , a, b, c, aa, bb, cc, aaa, aba, aca, bab, bbb, bcb, cac, cbc, ccc,
aaaa, abba, acca, baab, bbbb, bccb, caac, cbbc, cccc, . . ..
Soit lalphabet = 0, 1. Lensemble constitue des ecritures binaires
10
des
entiers positifs pairs est un langage sur
10, 100, 110, 1000, 1010, 1100, 1110, . . .
de meme que le langage forme des ecritures binaires des nombres premiers
10, 11, 101, 111, 1011, 1101, 10001, . . ..
Passons ` a present en revue quelques operations sur les langages. Tout
dabord, puisquun langage est un ensemble, on dispose des operations en-
semblistes usuelles comme lunion, lintersection ou encore la complementa-
tion.
Denition I.2.3. Soient L, M
w0 {0, 1}
represente lentier n si n =
P
i=0
wi2
i
. En general,
on ne consid`ere que des mots dont le premier symbole w
. Letoile de Kleene
11
de L est donnee par
L
=
_
i0
L
i
.
Ainsi, les mots de L
introduite precedem-
ment est coherente puisquil sagit en fait de letoile de Kleene du langage
ni . On dit parfois que
. Dune mani`ere
generale, si L est un langage ne contenant pas le mot vide, alors L
+
=
L
.
Proposition I.2.8. Soit L
un langage. Le langage L
est le plus
petit
12
langage M tel que M, L M et M
2
M.
11
Stephen Cole Kleene (19091994), logicien, est, avec K. Godel, A. Turing, A.
Church, E. Post, lun des p`eres fondateurs de linformatique theorique. On lui doit notam-
ment le concept dexpression reguli`ere. S.C. Kleene, Representation of Events in Nerve
Nets and Finite Automata, Automata Studies, Princeton, Princeton University Press,
(1956) Ed. C. Shannon, J. McCarthy.
12
Le plus petit pour linclusion.
I.2. Langages 13
Demonstration. Il est clair que L
M. Puisque
L M et M
2
M, on en conclut que L
2
M. De proche en proche, on
saper coit que
L
i
M, i > 0.
Ceci conclut la preuve.
= F
.
Demonstration. Si L est ni, le resultat est immediat. Il sut de pren-
dre F = L. Sinon, considerons le mot non vide a
p
le plus court, p 1,
appartenant ` a L. Il est evident que a
p
a
p
. D`es lors,
q
1
= t
1
p +r
1
, avec 0 < r
1
< p et t
1
1.
En eet, q
1
> p et q
1
ne peut etre multiple de p. Nous avons ` a present que
a
p
, a
q
1
,= L
, il
existe un mot le plus court a
q
2
appartenant ` a L
a
p
, a
q
1
tel que
q
2
= t
2
p +r
2
, avec 0 < r
2
< p, r
2
,= r
1
et t
2
t
1
.
En eet, q
2
> q
1
et si r
2
= r
1
, alors on aurait
q
2
= (t
2
t
1
) p +t
1
p +r
1
. .
=q
1
.
Cela signierait alors que a
q
2
appartient ` a a
p
, a
q
1
,= a
p
, a
q
1
, a
q
2
.
Cependant, on remarque quil y a au plus p1 restes non nuls distincts lors
dune division euclidienne par p. Par consequent, on ne saurait eectuer ce
raisonnement indeniment et nalement
L
= a
p
, a
q
1
, . . . , a
qs
avec s p 1.
et
. On
remarque que f est compl`etement caracterise par les images de f sur les sym-
boles de . Si L est un langage sur , alors limage de L par le morphisme
f est
f(L) = f(u)
[ u L.
De la meme mani`ere, si M est un langage sur , alors limage inverse de M
par le morphisme f est
f
1
(M) = u
[ f(u) M.
Exemple I.2.12. Soient = a, b, c, = , et f le morphisme deni
par
f(a) = , f(b) = , f(c) = .
Si L = ab, bc, cb, aaab, aaac, alors
f(L) = , , .
Si M = , , , alors
f
1
(M) = ab, ac, ba, ca, bab, bac, cab, cac.
Dans notre exemple, pour tout , [f()[ = 1. Neanmoins, on peut
en toute generalite considerer un morphisme dont les images des lettres de
lalphabet dorigine seraient de longueurs dierentes.
Remarque I.2.13. Il arrive, dans de nombreuses situations, quon dis-
tingue le cas o` u il existe tel que f() = (on parle de morphisme ef-
fa cant), du cas o` u, pour tout , f() ,= (on utilise d`es lors lexpression
morphisme non ea cant).
Dans la section precedente, on a introduit le miroir dun mot. Cette
operation setend naturellement aux langages.
Denition I.2.14. Le miroir dun langage L est
L
R
= u
R
[ u L.
On peut avoir L = L
R
sans pour autant que les mots de L soient tous
des palindromes.
Denition I.2.15. La cl oture commutative dun langage L
est denie
par
Com(L) = w
[ u L : , [w[
= [u[
.
Cela signie que Com(L) contient les mots obtenus en permutant les lettres
des mots de L. Par exemple, si L = ab, bac, ccc, alors
Com(L) = ab, ba, abc, acb, bac, bca, cab, cba, ccc.
I.3. Expressions reguli`eres et langages associes 15
En utilisant la fonction de Parikh introduite ` a la denition I.1.4, il est clair
que
Com(L) =
1
(L).
Si L est un langage tel que Com(L) = L, alors L est dit commutatif.
Voici une derni`ere operation sur les mots et les langages.
Denition I.2.16. Le shue
13
de deux mots u et v est le langage
u.. v = u
1
v
1
u
n
v
n
[ u = u
1
u
n
, v = v
1
v
n
, u
i
, v
i
, n 1.
Par exemple
14
, si u = ab et v = cde, alors
u.. v = abcde, acbde, acdbe, acdeb, cabde,
cadbe, cadeb, cdabe, cdaeb, cdeab.
Le shue de deux langages se denit comme suit,
L.. M =
_
uL,
vM
u.. v.
3. Expressions reguli`eres et langages associes
La notion dexpression reguli`ere est dusage frequent en informatique.
En eet, on a souvent recours aux expressions reguli`eres lorsquon desire
rechercher certains motifs recurrents. Un exemple banal est celui dun reper-
toire contenant divers chiers :
> ls monrepertoire/
memoire.aux memoire.tex picture001.jpg rapsody.jpg
memoire.dvi picture001.jpg presentation.exe raw.jpg
memoire.old picture002.jpg price-list.txt
memoire.log picture003.jpg taches.txt
Si lutilisateur desire acher uniquement les images au format JPEG et
comportant lextension .jpg, il aura par exemple recours ` a une commande
comme
ls *.jpg
De la meme mani`ere, sil veut eacer tous les chiers relatifs ` a memoire, il
executera
rm m*
On pourrait imaginer, dans un repertoire plus fourni, vouloir selectionner
des chiers dont les noms satisfont ` a des crit`eres plus ns. Nous allons voir
comment denir ce genre de crit`eres dans le formalisme developpe lors des
precedentes sections.
13
On pourrait tenter de traduire ce terme par melange. Nous avons choisi de con-
server la denomination anglo-saxonne.
14
Nous avons pris ici deux mots nayant aucune lettre en commun pour rendre
lexemple plus simple. En toute generalite, on peut bien s ur prendre des mots posse-
dant les memes lettres.
16 Chapitre I. Mots et langages
Denition I.3.1. Soit un alphabet. Supposons que 0, e, +, ., (, ),
sont
des symboles nappartenant pas ` a . Lensemble
,
pour tout , appartient ` a
,
si et appartiennent ` a
, alors
( +) appartient ` a
,
(.) appartient ` a
appartient ` a
.
Exemple I.3.2. Si = a, b, voici quelques exemples dexpressions regu-
li`eres :
1
= (e + (a.b)),
2
= (((a.b).a) +b
3
= ((a +b)
.(a.b)).
A une expression reguli`ere, on associe un langage gr ace ` a lapplication
15
L :
par
L(0) = , L(e) = ,
si , alors L() = ,
si et sont des expressions reguli`eres,
L[( +)] = L() L(),
L[(.)] = L()L(),
L(
) = (L())
.
Exemple I.3.3. Poursuivons lexemple I.3.2. On a
L(
1
) = , ab,
L(
2
) = (aba b
,
L(
3
) = a, b
ab.
Denition I.3.4. Un langage L sur est regulier sil existe une expression
reguli`ere
telle que
L = L().
Si et sont deux expressions reguli`eres telles que L() = L(), alors on
dit que et sont equivalentes.
Remarque I.3.5. Dans la suite, on sautorisera ` a confondre une expression
reguli`ere et le langage quelle represente. Si aucune confusion nest possi-
ble, on sautorisera egalement ` a enlever les parenth`eses ou autres symboles
superus. Par exemple,
(((b
.a).(b
.a))
.b
) = (b
a b
a)
15
La notation 2
).
I.3. Expressions reguli`eres et langages associes 17
represente le langage forme des mots sur a, b comprenant un nombre pair
de a. On se convainc aisement que ce langage est aussi represente par
lexpression
b
(a b
a b
.
Proposition I.3.6. Lensemble L(
ou . Par
consequent, L appartient ` a /.
Si = ( +) avec et des expressions reguli`eres sur de longueur
inferieure ` a celle de , alors on a
L() = L() L().
Par hypoth`ese de recurrence, L() et L() appartiennent ` a /. Puisque /
est stable pour lunion, on en conclut que L appartient ` a /.
Si = (.) ou =
=
0
+
1
+ +
k
+
k+1
,
( +)
= (
.
Dans le cas particulier dun alphabet unaire (i.e., contenant un seul
symbole), on dispose dune caracterisation des langages reguliers.
16
On peut denir la longueur dune expression reguli`ere de la mani`ere suivante. Soient
, deux expressions reguli`eres. Si = 0, e ou ( ), alors || = 1. De plus,
|( +)| = || +|| + 1, |(.)| = || +|| + 1 et |
| = || + 1.
18 Chapitre I. Mots et langages
Proposition I.3.9. Soit = . Les langages reguliers sur sont
exactement les langages de la forme
i
[ i A
o` u A N est une union nie de progressions arithmetiques.
Rappelons quune progression arithmetique est un ensemble de la forme
p +N.q = p +n.q [ n N
avec p, q N.
Demonstration. Nous avons dej` a remarque (cf. exemple I.1.14) que
lapplication longueur est un morphisme de monodes entre (
, .) et (N, +).
Ici, lapplication
[ [ :
N :
n
n
est meme un isomorphisme
17
de monodes. Lensemble T des unions nies
de progressions arithmetiques jouit des proprietes suivantes :
T (cas de lunion vide),
1 T car 1 = 1 +N.0,
lunion de deux elements de T est encore un element de T (en
eet, lunion de deux unions nies de progressions arithmetiques
est encore une union nie de progressions arithmetiques),
la somme de deux elements de T est encore un element de T. Pour
le verier, puisque T est stable pour lunion, il sut de considerer
le cas de deux progressions arithmetiques p + N.q et r + N.s. Si
q = 0, alors
(p +N.q) + (r +N.s) = (r +p) +N.s T.
Si q > 0, alors
(p +N.q) + (r +N.s) =
_
0i<q
((p +r +i s) +N.q) T.
Il est clair que le membre de droite est inclus dans le membre de
gauche. Montrons lautre inclusion. Soit t (p +N.q) + (r +N.s).
Il existe m, n N tels que t = p + r + mq + ns. Si on eectue la
division euclidienne de n par q, il existe et i tels que
n = q +i, 0 i < q.
Par consequent,
t = p +r +mq + ( q +i) s = p +r +i s + (m + s) q
avec 0 i < q.
17
Un isomorphisme est un morphisme bijectif. Il est clair que nous avons une bijection
uniquement dans le cas dun alphabet unaire. En eet, si = {a, b}, alors |ab| = |ba| = 2
mais ab = ba et lapplication longueur nest donc pas injective.
I.3. Expressions reguli`eres et langages associes 19
On peut denir letoile dune partie A de N par
A
= a
1
+ +a
n
[ n N et i 1, . . . , n, a
i
A.
En particulier, 0 appartient toujours ` a A
= A
+B
= p +n
1
q + +p +n
j
q [ n
1
, . . . , n
j
N, j > 0 0.
Si p = 0, (N.q)
= q
= N.q T. Si p > 0,
(p +N.q)
= 0
_
0i<p
((p +i q) +N.p).
Il est clair que le membre de droite est inclus dans le membre de
gauche. Verions lautre inclusion. Soit j > 0. On a
p +n
1
q + +p +n
j
q = p + (j 1) p + (n
1
+ +n
j
) q.
En eectuant la division euclidienne de n
1
+ +n
j
par p, on trouve
n
1
+ +n
j
= mp +i, avec 0 i < p
et donc
p +n
1
q + +p +n
j
q = p +i q + (j 1 +mq) p
avec 0 i < p.
Supposons ` a present que Q 2
N
est une famille de parties de N qui
contient et 1 et qui est stable pour lunion, la somme et letoile. Montrons
que T Q. Puisque Q est stable pour lunion, il sut de montrer que les
progressions arithmetiques de la forme p +N.q, p, q N, appartiennent ` a Q.
Puisque Q, on a
= 0 Q. En outre, 1 Q et en utilisant le
fait que Q est stable pour laddition, on voit que r appartient ` a Q pour
tout r > 0. On en deduit que, pour tous p, q N,
p +N.q = p +q
appartient ` a Q.
On conclut en utilisant la proposition I.3.6 et le fait que lapplication
longueur est un isomorphisme entre (N, +) et (
, .).
_
_
xX
Nx<N+p
(x +N.p)
_
.
Reciproquement, si
X =
n
_
i=1
(q
i
+N.p
i
),
alors en posant p = ppcm
i=1,...,n
p
i
et N = max
i=1,...,n
q
i
, il est clair que
n N, n X n +p X.
N
p
0 1 2 3 4
Figure I.4. Preperiode et periode.
I.3. Expressions reguli`eres et langages associes 21
Exemple I.3.13. Utilisons la proposition I.3.9 pour montrer que le langage
L = a
n
2
[ n N
nest pas regulier. En eet, si ce langage etait regulier, alors
[L[ = n
2
[ n N
serait une union nie de progressions arithmetiques de la forme
A =
I
_
i=1
r
i
+N.s
i
avec au moins un des s
i
non nul. Il est clair que la dierence entre deux
elements consecutifs de A est majoree par une constante
C supr
1
, . . . , r
I
, s
1
, . . . , s
I
) est deni
comme etant le plus petit ensemble de langages contenant , les langages
nis et qui est stable pour les operations rationnelles dunion, de concatena-
tion (produit considere sur le monode
= a
1
a
p
[ p 1, 1 i p, a
i
A 1
M
, i.e.,
A
tels que w = v et w
R
= v
R
. Montrer que cette
denition est equivalente ` a celle qui suit : si w = , alors w
R
= ; sinon, il
existe et v
tels que w = v et w
R
= v
R
. Demontrer que pour
tous u, v, w
,
(w
R
)
R
= w et (uv)
R
= v
R
u
R
.
Exercice I.4.2. Demontrer que pour tous u, v, w
, on a
uw = vw u = v
et
wu = wv u = v.
Exercice I.4.3. Soient x, y, u, v des mots sur un alphabet tels que xy =
uv. Demontrer que
si [x[ > [u[, alors il existe w ,= tel que x = uw et v = wy,
si [x[ = [u[, alors x = u et y = v,
si [x[ < [u[, alors il existe w ,= tel que u = xw et y = wv.
Exercice I.4.4. Il est clair que pour tout mot w, #(Pref(w)) = [w[ + 1.
Quelles sont les bornes (inferieures et superieures) exactes pour #(Fac(w)).
Exercice I.4.5. Soit = a, b un alphabet. Quels sont les mots w
pour lesquels w
2
= w
3
?
Exercice I.4.6. Soit = a, b un alphabet. Quels sont les mots w
tel que w
3
= v
2
?
Exercice I.4.7. Caracteriser les mots w tels que w = w
R
(i.e., les palin-
dromes).
Exercice I.4.8. Soit L
un langage. Si L = L
R
, cela implique-t-il
que tous les mots du langage sont des palindromes ? Justier votre reponse
et envisager egalement le cas particulier dun alphabet unaire.
I.4. Exercices 23
Exercice I.4.9. Soit le langage L a, b
= L
, L
= L
, L
L = L
= LL
.
A-t-on toujours LL
= L
?
Exercice I.4.12. Soient L, M, N des langages sur un alphabet . Montrer
que L(M N) LM LN. Montrer quen general, lautre inclusion est
fausse.
Exercice I.4.13. Soient L = aa, bb et M = , b, ab.
Enumerer les mots de LM et L.. M.
Enumerer les mots de M
?
Combien de mots de longueur n N poss`ede le langage L
?
Exercice I.4.14. Soient L et M deux langages nis. A-t-on toujours
#L.#M = #(LM) ?
Justier votre reponse.
Exercice I.4.15. Soient des alphabets disjoints et . Pour m, n N,
on note
t(m, n) := #(u.. v), u
m
, v
n
.
Montrer que
t(m, n) = t(m, n 1) +t(m1, n), m, n > 0
et que t(m, 0) = t(0, m) = 1. Utiliser cette formule pour en deduire la valeur
de
#(abba .. cd).
24 Chapitre I. Mots et langages
Pour calculer t(m, n) au moyen de la formule donnee ci-dessus, combien
detapes sont necessaires ?
Exercice I.4.16. Soit = a, b un alphabet binaire. Un mot w
est
sans carre sil ne contient aucun facteur de la forme xx avec x un mot non
vide. Enumerer tous les mots sans carre de
tel que w = u
i
, pour un i 1. Demontrer quun
mot est primitif si et seulement si il est egal ` a sa propre racine primitive.
Exercice I.4.18. Deux mots u et v sur sont conjugues sil existe x, y
) qui
est telle que L(
+
) = (L())
+
=
i>0
(L())
i
. Demontrer que
(ba)
+
(a
+a
) = (ba)
b a
+
(b
+e),
b
+
(a
+e)b = b(b
+e)b
+
,
(a +b)
= (a +b)
,
(a +b)
= (a
+ba
,
(a +b)
= (b
(a +e)b
.
Exercice I.4.36. Soit = a, b. Verier que
(ab)
+
= (a
b) (
aa
bb
).
4.3. Langages reguliers sur un alphabet unaire.
Exercice I.4.37. Exprimer [L()[ comme une union nie de progressions
arithmetiques lorsque
= (ab)
+bbb,
= (a(ba
) +a
,
= (ab)(ac(a +b))
,
= ab(bbc)
.
26 Chapitre I. Mots et langages
Exercice I.4.38. Construire une expression reguli`ere telle que
[L()[ = 5 +N.3,
[L()[ = N.7 (4 +N.5).
Exercice I.4.39. Le langage a
n
3
+2n+1
[ n N est-il regulier ? Justier.
Exercice I.4.40. Le langage a
2n+1
[ n N est-il regulier ? Justier.
Exercice I.4.41. Le langage a
n
[ n T o` u T designe lensemble des
nombres premiers est-il regulier ? Justier.
Remarque I.4.42. Le resultat obtenu ` a lexercice precedent nest en rien
incompatible avec le cel`ebre theor`eme de Dirichlet qui stipule que si a et b
sont premiers entre eux (i.e., pgcd(a, b) = 1), alors la progression arithme-
tique a +N.b contient une innite de nombres premiers.
CHAPITRE II
Automates
Nous avons vu au premier chapitre que les expressions reguli`eres permet-
tent de generer ce que lon a decide dappeler les langages reguliers. Les
automates que nous allons introduire ici sont des machines permettant
de reconnatre exactement ces langages. En dautres termes, lensemble des
langages acceptes par automate ni concide avec lensemble des langages
reguliers.
1. Automates nis deterministes
Denition II.1.1. Un automate ni deterministe (ou AFD) est la donnee
dun quintuple
/ = (Q, q
0
, F, , )
o` u
Q est un ensemble ni dont les elements sont les etats de /,
q
0
Q est un etat privilegie appele etat initial,
F Q designe lensemble des etats nals,
est lalphabet de lautomate,
: Q Q est la fonction de transition de /.
Nous supposerons que est une fonction totale, i.e., que est deni pour
tout couple (q, ) Q (on parle alors dAFD complet).
Nous representons un AFD / de la mani`ere suivante. Les etats de /
sont les sommets dun graphe oriente et sont representes par des cercles. Si
(q, ) = q
, q, q
et de
label
q
q
.
Les etats nals sont reperes gr ace ` a un double cercle et letat initial est
designe par une `eche entrante sans label. Enn, si deux lettres et
sont
telles que (q, ) = q
et (q,
) = q
.
Cette convention sadapte aisement ` a plus de deux lettres.
27
28 Chapitre II. Automates
Exemple II.1.2. Lautomate / = (Q, q
0
, F, , ) o` u Q = 1, 2, 3, q
0
= 1,
F = 1, 2, = a, b et o` u la fonction de transition est donnee par
a b
1 1 2
2 1 3
3 3 2
est represente ` a la gure II.1.
1
a
b
2
a
b
3
a
b
Figure II.1. Un AFD.
Denition II.1.3. Soit / = (Q, q
0
, F, , ) un AFD. On etend naturelle-
ment la fonction de transition ` a Q
de la mani`ere suivante :
(q, ) = q
et
(q, w) = ((q, ), w), , w
.
Le langage accepte par / est alors
L(/) = w
[ (q
0
, w) F.
Si w L(/), on dit encore que / accepte le mot w (ou que w est accepte
par /).
Ainsi, le r ole fondamental dun automate est daccepter ou de rejeter
des mots. Un automate partitionne lensemble des mots sur en deux
sous-ensembles
L(/) et
L(/).
Exemple II.1.4. Si on poursuit lexemple precedent, lautomate / de la
gure II.1 accepte le mot abbab car on a, partant de letat initial, le parcours
suivant au sein de / :
1
a
1
b
2
b
3
a
3
b
2 F.
Par contre, bba nest pas accepte par / car
1
b
2
b
3
a
3 , F.
Exemple II.1.5. Lautomate / represente ` a la gure II.2 accepte exac-
tement le langage forme des mots sur lalphabet a, b et contenant un nom-
bre impair de a.
L(/) = w a, b
: [w[
a
1 (mod 2).
II.2. Automates non deterministes 29
1
b
a
2
b
a
Figure II.2. Un automate ni deterministe.
Remarque II.1.6. Pour simplier les notations, on sautorise ` a ecrire
q.w
au lieu de (q, w) si aucune confusion nest possible.
Denition II.1.7. A tout mot w de
, q
1
, . . . , q
Q
tels que
(q
0
, v
1
, q
1
), (q
1
, v
2
, q
2
), . . . , (q
1
, v
, q
) ,
w = v
1
v
et q
F.
En dautres termes, cette condition signie quil existe un chemin dans le
graphe associe ` a / debutant dans un etat initial, de label w et se terminant
dans un etat nal. Naturellement, le langage accepte par un AFND / est
lensemble des mots acceptes par / et se note encore L(/). Enn, deux
AFND / et B sont dits equivalents si L(/) = L(B).
Exemple II.2.4. Si nous poursuivons lexemple II.2.2, le mot ab est ac-
cepte car 1 I, (1, a, 3) , (3, b, 2) et 2 F. Ceci se note schema-
tiquement,
1
a
3
b
2.
A un mot, il peut correspondre plus dun chemin. Par exemple, au mot
baa, il correspond les chemins
3
b
2
a
1
a
1,
3
b
2
a
1
a
3
et
1
ba
2
a
1.
Ce sont les trois seules possibilites partant dun etat initial. Le mot baa
nest donc pas accepte par lautomate.
II.2. Automates non deterministes 31
Remarque II.2.5. Dans la denition dun AFND, rien nempeche davoir
des transitions vides du type
(q, , q
) .
On parle parfois de -transitions. En particulier, on suppose implicitement
que pour tout etat q dun AFND, on a
(q, , q) .
Exemple II.2.6. Considerons lAFND suivant. Cet automate accepte le
1
a
2
b
3
a
) ,
[w[ 1.
Comme le montre le lemme suivant, on peut dans le cadre des AFND
se restreindre au cas dautomates elementaires. En eet, tout AFND est
equivalent ` a un AFND elementaire.
Lemme II.2.8. Tout langage accepte par un AFND est accepte par un
AFND elementaire.
Demonstration. Soit / = (Q, I, F, , ) un AFND. Sil nest pas elemen-
taire, il existe au moins un mot w = w
1
w
k
(k 2, w
i
) et des etats
q, q
tels que
(q, w, q
) .
Considerons de nouveaux etats q
1
, . . . , q
k1
nappartenant pas Q. Il est clair
que lautomate B = (Q
, I, F, ,
) o` u
Q
= Q q
1
, . . . , q
k1
et
=
_
(q, w, q
)
_
_
_
(q, w
1
, q
1
), (q
1
, w
2
, q
2
), . . . , (q
k2
, w
k1
, q
k1
), (q
k1
, w
k
, q
)
_
32 Chapitre II. Automates
est tel que L(/) = L(B). En repetant cette procedure pour chaque transition
(q, w, q
,
(G, uv) = ((G, u), v).
Si au moins un des deux mots u ou v est nul, la conclusion est immediate.
Sinon, nous devons montrer que
G.uv = (G.u).v.
Il est clair que le membre de droite est inclus dans le membre de gauche.
Lautre inclusion resulte du fait que lautomate est elementaire. En ef-
fet, cette propriete est indispensable. En guise dillustration, lautomate
represente ` a la gure II.7 nest pas elementaire et 1.ab = 3, 4, 1.a =
2
M. O. Rabin, D. Scott, Finite automata and their decision problems, IBM J. of
Research and Development 3 (1959), 114125.
3
B est ni car #2
Q
= 2
#Q
et A est ni.
34 Chapitre II. Automates
1 2
b
3
a
4
ab
Figure II.7. Un automate non elementaire.
2 et (1.a).b = 2.b = 3 donc
1.ab , (1.a).b.
Pour un AFND elementaire, les arcs ayant des labels de longueur au plus
un, une telle situation ne peut se produire.
Il nous reste ` a montrer que L(/) = L(B). On proc`ede par double
inclusion. Soit w appartenant ` a L(/). Cela signie quil existe dans /
un chemin de label w debutant dans un etat initial de I (et meme dans un
etat de I.) et aboutissant dans un etat nal de F. En dautres termes, par
denition de Q
0
,
Q
0
.w F ,=
et (Q
0
, w) appartient donc ` a F.
Soit w appartenant ` a L(B). Dans B, le chemin de label w debutant dans
Q
0
aboutit dans un etat nal de F, i.e.,
(Q
0
, w) F.
Donc
(I.).w F ,=
ce qui signie que w est accepte par /.
.
donne
X X.a X.b
A = 1, 2, 4 3, 4
B = 3, 4 4 2
C =
D = 4 4
E = 2 3
F = 3 2
et on trouve lautomate de la gure II.11.
Remarque II.2.15. Il est clair que tout AFD est un cas particulier dAFND.
Par consequent, tout langage accepte par un AFD / est trivialement accepte
par un AFND (` a savoir / lui-meme). De la proposition II.2.11, nous con-
cluons donc que les langages acceptes par les AFD et les AFND concident.
Nous pourrons d`es lors, par la suite, parler dun langage accepte par un
automate ni (sans autre precision).
2.1. A propos de lexplosion exponentielle. Le nombre detats
peut crotre de mani`ere exponentielle lorsquon rend deterministe un AFND.
Dans certaines situations, cette explosion du nombre detats est inevitable
et ce, meme dans le cas dun alphabet unaire.
Denition II.2.16. On denit un AFND /
k
sur un alphabet unaire a
comme suit. Cet automate poss`ede un unique etat initial ` a partir duquel
on peut se deplacer dans k boucles disjointes. Pour i = 1, . . . , k, la i-i`eme
II.2. Automates non deterministes 37
a
b
a,b
a
a b
a
b
b
a
b
A B D
C E
F
Figure II.11. un AFD acceptant a(ba)
.
boucle est un cycle de longueur p
i
o` u p
i
represente le i-`eme nombre premier.
Les etats nals sont letat initial et un etat par cycle, de mani`ere telle que
le langage accepte par /
k
soit
L(/
k
) = a
n
[ n N.p
1
N.p
2
. . . N.p
k
=: L
k
.
Un exemple, dans le cas k = 3, est represente ` a la gure II.12.
a
a
a
a
a
a
a
a
a a
a
a
a
Figure II.12. Lautomate /
3
.
Proposition II.2.17. Le langage L
k
accepte par lAFND /
k
possedant
1 + p
1
+ p
2
+ + p
k
etats est accepte par un AFD ayant N = p
1
p
2
p
k
etats et aucun AFD ayant moins de N etats naccepte ce langage.
Demonstration. Tout dabord, un AFD compose dun unique cycle de
longueur N convient. En eet, si on numerote les etats de cet automate
0, . . . , N 1, alors letat initial est 0 et les etats nals correspondent aux
indices i pour lesquels il existe j 1, . . . , k tel que
i 0 (mod p
j
).
38 Chapitre II. Automates
Il est clair quun tel AFD accepte exactement L
k
. Par exemple, dans le cas
o` u k = 3, on a lAFD represente ` a la gure II.13. Dans cet automate, est
nal tout etat dont lindice est multiple de 2, 3 ou 5.
7
13
11
1
17
19
29
23
Figure II.13. Un AFD acceptant L
3
.
A present, supposons que B est un AFD acceptant L
k
et poss`edant
moins de N etats. Puisque lalphabet est unaire, cet automate est de la
forme suivante :
Figure II.14. Un AFD sur un alphabet unaire.
On parle parfois de mani`ere imagee, dautomate poele ` a frire (frying pan
automaton). Le cycle est de longueur 1 et le chemin menant au cycle
est de longueur c 0. Par hypoth`ese, on a < N. Par consequent, il
existe j 1, . . . , k tel que p
j
soit premier avec (en eet, sinon, p
1
, . . . , p
k
apparatraient tous dans la decomposition en facteurs premiers de et d`es
lors, on aurait N). Par le theor`eme de Bezout, il existe f, g Z tels que
f p
j
+g = 1.
En dautres termes,
f p
j
1 (mod )
et donc
mp
j
(mod ) [ m N = 0, . . . , 1.
On a bien s ur aussi, quel que soit c,
(3) mp
j
c (mod ) [ m N = 0, . . . , 1.
II.3. Stabilite des langages acceptes par automate 39
Cela signie que pour accepter les mots de la forme a
n
avec n = c + c
multiple de p
j
, le cycle de lautomate B doit avoir tous ses etats nals. En
eet, c
est de la forme mp
j
c, m N, et donc, vu (3), la lecture dun
tel mot a
n
peut aboutir dans un etat quelconque du cycle. D`es lors, cet
automate B accepte tout mot a
t
pour t c et en particulier, il accepte les
mots de longueur
p
n
k+1
pour n susamment grand. Or il est facile de voir que ces derniers mots
nappartiennent pas ` a L
k
. En eet, les puissances de p
k+1
ne peuvent etre
multiples de p
1
, . . . , p
k
. Ainsi, lautomate B ne peut accepter L
k
.
i=1
p
i
1
2
k
2
log k
alors quune minoration grossi`ere donne
p
1
p
k
2
k
.
3. Stabilite des langages acceptes par automate
Nous montrons tout dabord que lensemble des langages acceptes par
un automate ni est stable pour les operations rationnelles (i.e., lunion, la
concatenation et letoile de Kleene).
Proposition II.3.1. Si L et M sont les langages acceptes par deux auto-
mates nis, alors L M est aussi accepte par un automate ni.
Demonstration. Representons symboliquement un automate ni / par
le schema donne ` a la gure II.15. On represente uniquement les etats nals
q
0
A
F
Figure II.15. Representation symbolique dun automate.
et letat initial. Pour ne pas alourdir le dessin, on ne represente aucune des
transitions. De plus, rien nempeche letat initial detre nal. Considerer un
seul etat initial nest pas en soi une restriction. En eet, on peut ajouter
un nouvel etat q
0
` a un automate. Cet etat est considere comme le seul etat
initial et on place une -transition depuis q
0
vers chacun des anciens etats
4
cf. E. Bach et J. Shallit, algorithmic number theory, Vol.1, Ecient algorithms,
Foundations of Computing Series, MIT Press, 1996.
40 Chapitre II. Automates
initiaux (qui perdent alors ce statut particulier). De la sorte, on obtient un
automate equivalent avec un seul etat initial.
A
F
q
0
lest
aussi.
5
Sans autre precision, on peut considerer des AFD ou des AFND.
II.3. Stabilite des langages acceptes par automate 41
F B A
F
est
aussi accepte par un automate ni.
Demonstration. Soit / un automate ni. Sans perte de generalite, on
suppose / elementaire
6
. Le morphisme f est compl`etement deni par les
valeurs quil attribue aux elements de . Le langage f(L) est accepte par
lautomate /
par
q
f()
q
.
Rien nassure que lautomate /
). En eet, si
6
Nous laissons au lecteur le soin de verier que la construction proposee dans cette
preuve peut aussi etre utilisee dans le cas dun automate non elementaire.
42 Chapitre II. Automates
w = w
1
w
k
est accepte par /, il existe un chemin debutant dans letat
initial
q
0
w
1
q
1
w
2
q
2
q
k1
w
k
q
k
tel que q
k
soit un etat nal de /. A ce chemin, il correspond dans /
le
chemin
q
0
f(w
1
)
q
1
f(w
2
)
q
2
q
k1
f(w
k
)
q
k
et donc, f(w
1
w
k
) = f(w
1
) f(w
k
) est accepte par /
. Reciproquement,
` a tout mot v accepte par /
Proposition II.3.5. Si L
L(/).
.
Par contre, si on inverse le statut nal/non nal des etats, on obtient un
a,b
a
b
a
Figure II.20. Un AFND acceptant a(ba)
.
automate acceptant aa, b
.
Proposition II.3.7. Si L est un langage accepte par un automate ni, alors
L
R
est aussi accepte par un automate ni.
Demonstration. Soit / = (Q, I, F, , ) un AFND acceptant L. Lauto-
mate
A
R
= (Q, F, I, ,
R
)
o` u
R
est deni par
(q, w, q
) (q
, w
R
, q)
R
,
II.4. Produit dautomates 43
est un automate acceptant L
R
. En eet, si un mot est accepte par /, cela
signie quil existe un chemin de label w debutant dans un etat de I et
aboutissant dans un etat de F. Ainsi, par denition dans /
R
, on a un
chemin de label w
R
debutant dans un etat de F (ensemble des etats initiaux
de /
R
) et aboutissant dans un etat de I (ensemble des etats nals de /
R
).
Ainsi, w
R
est accepte par /
R
. La reciproque sobtient de mani`ere analogue.
= (Q, q
0
, F
, , ),
o` u F
tel que q = q
0
.w. Nous
laissons au lecteur le soin de verier que lAFND /
= (Q, I, F, , ), o` u
I est lensemble des etats simultanement accessibles et coaccessibles de /,
accepte Su(L).
), ) (
(a)
(q, ),
(b)
(q
, )).
Les mots acceptes par T sont exactement les mots w
tels que
((q
(a)
0
, q
(b)
0
), w) F
(a)
F
(b)
;
ceci est equivalent ` a
(a)
(q
(a)
0
, w) F
(a)
et
(b)
(q
(b)
0
, w) F
(b)
et signie que le langage accepte par T est L(/) L(B).
(a)
(b)
= .
Comme dans la preuve precedente, considerons un automate T ayant
Q
(a)
Q
(b)
comme ensemble ni detats,
(q
(a)
0
, q
(b)
0
) comme etat initial,
F
(a)
F
(b)
comme ensemble detats nals,
(a)
(b)
comme alphabet
et dont la fonction de transition : (Q
(a)
Q
(b)
)(
(a)
(b)
) (Q
(a)
Q
(b)
)
est denie par
: ((q, q
), )
_
(
(a)
(q, ), q
) si
(a)
(q,
(b)
(q
, )) si
(b)
.
Par construction, il est clair que L(T) = L(/) .. L(B). En eet, en lisant
un mot w, on ne peut atteindre un etat nal de T que si apr`es avoir lu toutes
les lettres de
(a)
(resp. de
(b)
) apparaissant dans w, on se trouve dans un
etat de T dont la premi`ere (resp. seconde) composante est dans F
(a)
(resp.
F
(b)
).
7
Ceci est toujours possible car sils avaient des alphabets dierents, il surait de
considerer comme alphabet commun, lunion des deux alphabets.
II.4. Produit dautomates 45
Il nous reste ` a envisager le cas o` u les alphabets ne sont pas disjoints.
Dans cette situation, on peut remplacer, par exemple,
(b)
=
1
, . . . ,
n
(b)
=
. On applique d`es lors la construction presentee ci-dessus. Pour terminer,
il sut dappliquer le morphisme f : (
(a)
(b)
)
(
(a)
(b)
)
deni
par
f(
i
) =
i
,
i
(b)
et f() = ,
(a)
.
On conclut en utilisant la proposition II.3.4.
et (cd)
acceptes respec-
tivement par les deux AFD de la gure II.21. Les tables de transition sont
2 1 3
a
b a
b
a,b
c
d
c,d
d
c
4 5
6
Figure II.21. AFD acceptant a
et (cd)
.
q q.a q.b
1 1 2
2 3 2
3 3 3
q q.c q.d
4 5 6
5 6 4
6 6 6
Recherchons la table de transition de lautomate acceptant le langage
(a
) ..(cd)
,
q q.a q.b q.c q.d
(1, 4) (1, 4) (2, 4) (1, 5) (1, 6)
(1, 5) (1, 5) (2, 5) (1, 6) (1, 4)
(1, 6) (1, 6) (2, 6) (1, 6) (1, 6)
(2, 4) (3, 4) (2, 4) (2, 5) (2, 6)
(2, 5) (3, 5) (2, 5) (2, 6) (2, 4)
(2, 6) (3, 6) (2, 6) (2, 6) (2, 6)
(3, 4) (3, 4) (3, 4) (3, 5) (3, 6)
(3, 5) (3, 5) (3, 5) (3, 6) (3, 4)
(3, 6) (3, 6) (3, 6) (3, 6) (3, 6)
Les etats nals sont (1, 4) et (2, 4), letat initial est (1, 4). Si on renumerote
les etats de 1 ` a 9 dans lordre du tableau, on a lAFD repris ` a la gure II.22.
46 Chapitre II. Automates
1
a
c
b
2
a
d
c
b
3
a,c,d
b
4
b
c
a
5
d
c
a
6
b,c,d
a
7
a,b
c
8
d
c
9
a,b,c,d
a,b
b
d
d
d
Figure II.22. AFD shue.
5. Exercices
Exercice II.5.1. Modeliser au moyen dun automate ni deterministe le
probl`eme du chou, de la ch`evre et du loup. Un berger doit faire traverser
une rivi`ere au moyen dune barque ` a un chou, une ch`evre et un loup. La
barque etant petite pour les transporter tous, ` a chaque trajet sur la rivi`ere,
il ne peut emporter quun seul des trois protagonistes. On ne peut laisser la
ch`evre et le chou (resp. le loup et la ch`evre) seuls sur une rive. Comment doit
faire le berger pour faire traverser les trois protagonistes sous les contraintes
indiquees. Avec la modelisation choisie, quel est le langage des deplacements
acceptables ?
Exercice II.5.2. Soit lAFD / = (Q, 1, F, , ) o` u Q = 1, 2, 3, =
a, b, F = 3 et o` u la fonction de transition est donnee par
a b
1 1 2
2 3 2
3 3 1
.
Tracer le diagramme detats de /. Donner lexecution de / sur les mots
abba,
bbbabb,
bababa,
bbbaa.
Quel est le langage accepte par / (en donner une expression reguli`ere) ?
Exercice II.5.3. Soient les langages a
et c. Construire un AFD
acceptant a
L
: N N : n #(L
n
).
Que vaut
a
b
(n) ? Meme question pour
a
{c}
(n).
Exercice II.5.4. Soient les deux AFD representes ` a la gure II.23. Construire
b
b
a
a
b
a a
b
a
b
Figure II.23. Deux automates nis deterministes.
un AFD acceptant le shue des langages acceptes par ces deux automates.
Exercice II.5.5. Soit lAFND represente ` a la gure II.24.
1
3
a
b
a
a
a
2
b
Figure II.24. Un AFND.
Enumerer les elements de la relation de transition de lautomate.
Quelles sont toutes les executions possibles du mot aaabb dans cet
automate (en demarrant de lunique etat initial).
Le mot aaabb est-il accepte ?
Rendre cet automate deterministe au moyen de la construction par
sous-ensembles detats.
Donner une expression reguli`ere du langage accepte par lautomate.
Exercice II.5.6. Rendre deterministe lautomate repris ` a la gure II.25.
(Prendre garde aux -transitions.)
Exercice II.5.7. Remplacer lautomate represente ` a la gure II.26 par un
automate equivalent possedant un unique etat initial et un unique etat nal.
Exercice II.5.8. Construire un AFND acceptant
(ab)
+a
.
Si lautomate obtenu nest pas deterministe, le rendre deterministe.
48 Chapitre II. Automates
1 2
3 4
,a
b
b a b
b
a
Figure II.25. Un AFND ` a rendre deterministe.
a
a
b
a
b
b
a
a
Figure II.26. Un AFND.
Exercice II.5.9 (Cet exercice pourra etre passe en premi`ere lecture, et
repris apr`es avoir vu la notion dautomate minimal). Montrer que pour tout
n 1, le langage (a+b)
b(a+b)
n1
peut etre reconnu par un AFND ` a n+1
etats, mais que tout AFD acceptant ce langage poss`ede au moins 2
n
etats.
Exercice II.5.10. Construire un AFND acceptant
(abc)
.
Si lautomate obtenu nest pas deterministe, le rendre deterministe.
Exercice II.5.11. En utilisant lexercice precedent, construire un AFD
acceptant le langage
((abc)
)
R
.
Exercice II.5.12. Construire un AFND acceptant
(ba +bb)
+ (ab +aa)
.
Si lautomate obtenu nest pas deterministe, le rendre deterministe.
Exercice II.5.13. Construire un AFND acceptant
(ab
+
a)
+
.
Si lautomate obtenu nest pas deterministe, le rendre deterministe.
Exercice II.5.14. Construire un AFD acceptant exactement les mots sur
a, b qui contiennent le facteur abba.
II.5. Exercices 49
Exercice II.5.15. Construire un AFD acceptant exactement les mots sur
a, b pour lesquels tout facteur de longueur 4 contient au moins un a.
Exercice II.5.16. Soit L a, b, c
: [w[
a
0 (mod 3),
w
: [w[
a
4,
Exercice II.5.18. Construire un AFD acceptant le langage
a
i
b
j
[ i j (mod 2).
Denition II.5.19. Soit p 2, tout entier n 1 se decompose de mani`ere
unique comme
n =
i=0
c
i
p
i
, avec c
i
0, . . . , p 1 et p
,= 0.
Le mot c
c
0
0, . . . , p 1
.
Exercice II.5.20. Soient k, m 2. Demontrer que k
n
(mod m) [ n N
est ultimement periodique.
Exercice II.5.21. Construire un AFD acceptant exactement les represen-
tations binaires des nombres pairs. (On suppose que 0 est represente par le
mot vide et pour des raisons de simplication, on autorise les zeros de tete
dans les representations, i.e., 000101 est par exemple une representation de
5.) Si besoin est, on permet de considerer les representations miroir.
Exercice II.5.22. Meme question avec les representations binaires des
multiples de 4, 5, 6 ou 7.
Exercice II.5.23. Donner la table de transition dun automate ni deter-
ministe reconnaissant les ecritures decimales des multiples de 6 (ou leur
miroir, si vous jugez la construction plus simple).
Remarque II.5.24. Ces trois derniers exercices montrent que tout crit`ere
de divisibilite peut toujours etre reconnu par un automate ni et ce, quelle
que soit la base choisie pour les representations des entiers.
50 Chapitre II. Automates
Exercice II.5.25. Soit = 0, 1. Si u
, alors on note
2
(u) lentier
represente par u en base 2. Par exemple,
2
(1101) = 13,
2
(001010) = 10.
On consid`ere lalphabet = . Construire un automate sur qui
reconnat le langage des couples (u, v) de mots de meme longueur tels que
2
(v) = 2
2
(u).
Pour obtenir des mots de meme longueur, on sautorise toujours ` a placer des
zeros de tete dans les representations. Par exemple,
_
0 1 0 1 0
1 0 1 0 0
_
appartient au langage accepte. Comme dans les exercices precedents, par
souci de simplication, on pourra dans un premier temps considerer les
representations miroir.
Exercice II.5.26. Dans le meme contexte que lexercice precedent, on note
=
3
. Construire un automate sur qui reconnat les triplets (u, v, w) de
mots de meme longueur tels que
2
(u) +
2
(v) =
2
(w).
Par exemple,
_
_
0 1 0 1 0
0 1 1 0 0
1 0 1 1 0
_
_
appartient au langage accepte. Comme dans les exercices precedents, par
souci de simplication, on pourra dans un premier temps considerer les
representations miroir.
Exercice II.5.27. Meme question qu` a lexercice II.5.25, mais cette fois,
on impose
2
(v) = 3
2
(u).
Exercice II.5.28. Montrer que le langage des representations binaires des
nombres entiers divisibles par 4 est regulier, en donnant une expression
reguli`ere.
Montrer que le langage des representations binaires des nombres entiers
divisibles par 3 est regulier, en fournissant un automate ni deterministe
acceptant ce langage (ou son miroir, au choix).
Deduire des deux premiers points que le langage des representations
binaires des nombres entiers divisibles par 12 est regulier ? Justier votre
reponse.
CHAPITRE III
Langages reguliers et automates
Le but premier de ce chapitre est de montrer que lensemble des langages
reguliers concide exactement avec lensemble des langages acceptes par au-
tomate ni. Nous allons donc faire le lien entre les notions introduites aux
deux premiers chapitres.
1. Des expressions aux automates
A toute expression reguli`ere , on peut associer un automate ni / de
telle sorte que L() = L(/). On proc`ede par recurrence sur la longueur de
.
Si = 0, les automates suivants acceptent tous deux le langage .
,...,
1 n
Figure III.1. AFD et AFND acceptant .
Si = e, les automates suivants acceptent le langage .
,...,
1 n
,...,
1 n
Figure III.2. AFD et AFND acceptant .
Si = , , les automates suivants acceptent le langage .
,...,
1 n
,...,
1 n
=
Figure III.3. AFD et AFND acceptant .
Si = ( + ), avec et des expressions reguli`eres de longueur
inferieure ` a celle de , alors, par hypoth`ese de recurrence, on dis-
pose de deux automates nis /
et /
acceptant respectivement
L() et L(). On conclut en utilisant la proposition II.3.1.
51
52 Chapitre III. Langages reguliers et automates
Si = (.), on utilise les memes raisonnements et la proposition
II.3.2.
Enn, si =
ba
b)
. Des auto-
mates acceptant L(a) = a et L(b) = b sont donnes par :
a b
Figure III.4. AFND acceptant a et b.
En utilisant la proposition II.3.3, on construit un automate acceptant a
:
a
.
Pour des raisons de simplications evidentes, nous allons considerer un au-
tomate equivalent acceptant aussi a
:
a
Figure III.6. AFND equivalent acceptant a
.
En utilisant la proposition II.3.2, on construit un automate acceptant a
b :
a
b
b.
III.1. Des expressions aux automates 53
En utilisant cette proposition une seconde fois, on obtient un automate
acceptant a
ba
b :
a
b
a
b
ba
b.
Et en simpliant quelque peu, on a meme
a
b
a
b
Figure III.9. AFND equivalent acceptant a
ba
b.
Appliquons ` a present la proposition II.3.3 ` a ce dernier automate pour obtenir
a
b
a
b
ba
b)
.
La derni`ere etape consiste ` a combiner lautomate ci-dessus avec celui
acceptant a
ba
b)
.
54 Chapitre III. Langages reguliers et automates
2. Des automates aux expressions reguli`eres
Nous denissons tout dabord des automates generalises dont les arcs
ont comme label non pas des lettres de lalphabet mais des expressions
reguli`eres. Pour rappel, on note
) = 0 si q ,= q
et (q, q
) = e si q = q
.
Exemple III.2.2. Lautomate represente ` a la gure III.12 est un AFE.
On a (1, 2) = ab
et des etats q
1
, . . . , q
n
Q tels que
w = w
1
w
n
,
w
1
L((q
0
, q
1
)), . . . , w
n
L((q
n1
, q
n
))
et q
n
F.
Par exemple, pour lAFE donne dans lexemple precedent, le mot w =
abbbbbabab est accepte car si on pose w
1
= abbbb, w
2
= ba et w
3
= bab, on
saper coit que w
1
L(ab
), w
2
L(a +ba) et w
3
L(bab).
Denition III.2.4. Le langage accepte par un AFE est lensemble des
mots quil accepte. Deux AFE sont dits equivalents sils acceptent le meme
langage.
Remarque III.2.5. Un AFD est un cas particulier dAFE o` u toutes les
transitions sont des expressions reguli`eres de la forme , . Ainsi, les
techniques decrites ci-apr`es peuvent sappliquer au depart dun AFD.
1
En anglais, on trouve la denomination extended nite automaton.
III.2. Des automates aux expressions reguli`eres 55
Dans les lignes qui suivent, nous allons expliquer comment, au depart
dun AFE arbitraire, obtenir un AFE equivalent possedant uniquement deux
etats (un initial et un nal). De cette mani`ere, il sera aise den deduire une
expression reguli`ere du langage accepte.
Le pivotage (Elimination dun etat qui nest ni initial, ni nal).
Soit / = (Q, q
0
, F, , ) un AFE. Pour tous p, q Q, on note r
pq
lexpression
reguli`ere (p, q). Soit q un etat de / tel que q ,= q
0
et q , F. Denissons
lAFE
/
= (Q
, q
0
, F, ,
)
o` u Q
= Q q et pour tous p, s Q
(p, s) = r
ps
+r
pq
r
qq
r
qs
.
Par construction, il est clair que /
est equivalent ` a /.
r
r
p
s
ps
ps
r + r r r
pq qq qs
*
p
s
r
pq
qq
r
qs
q
Figure III.13. Le pivotage.
Exemple III.2.6. Considerons lAFE donne ` a la gure III.14. Avec les
2 1 3
4
b
ab
b b
b
a a
Figure III.14. Un AFE avant elimination de letat 2.
notations precedentes, si on desire eliminer letat 2, on obtient
(1, 1) = r
11
+r
12
r
22
r
21
= e +a b
0 = e
(1, 3) = r
13
+r
12
r
22
r
23
= ab +a b
(1, 4) = r
14
+r
12
r
22
r
24
= 0 +a b
b = ab
(3, 1) = r
31
+r
32
r
22
r
21
= 0 + 0 b
0 = 0
(3, 3) = r
33
+r
32
r
22
r
23
= e + 0 b
a = e
(3, 4) = r
34
+r
32
r
22
r
24
= b + 0 b
b = b
(4, 1) = r
41
+r
42
r
22
r
21
= 0 +b b
0 = 0
(4, 3) = r
42
+r
42
r
22
r
23
= 0 +b b
a = bb
(4, 4) = r
44
+r
42
r
22
r
24
= e +b b
b = bb
b +e
56 Chapitre III. Langages reguliers et automates
En ne representant que les transitions dierentes de 0 et dierentes de
(q, q) = e, on obtient lAFE equivalent represente ` a la gure III.15.
1 3
4
ab+ab a *
b
*
bb a
ab b
*
bb b
*
Figure III.15. AFE equivalent apr`es elimination de letat 2.
Lalgorithme complet
2
Soit / = (Q, q
0
, F, , ) un AFE.
(1.a) Obtention dun etat initial non nal et au quel on ne peut
aboutir. Si letat initial q
0
est nal ou si il existe q Q tel que
3
(q, q
0
) ,= 0,
alors on ajoute un nouvel etat q
0
` a lensemble Q detats et on pose (q
0
, q
0
) =
e. On redenit q
0
comme le nouvel etat initial.
(1.b) Obtention dun unique etat nal. Si #F > 1, cest-` a-dire, sil y
a plus dun etat nal, on ajoute un nouvel etat f
et on pose (q, f
) = e
pour tout q F. Ensuite, on redenit f
= (Q
, q
0
, f
, ,
0
(non nal
et auquel naboutit aucune transition) et un unique etat nal f
.
(2) Fin ? Si Q
= q
0
, f
est
r
q
0
f
(r
f
f
)
o` u r
q
0
f
=
(q
0
, f
) et r
f
f
=
(f
, f
0
, f
. On elimine q de
/
(1, 1) = r
11
+r
13
r
33
r
31
= e + (ab +ab
a) e 0 = e
(1, 4) = r
14
+r
13
r
33
r
34
= ab
b + (ab +ab
a) e b
(4, 1) = r
41
+r
43
r
33
r
31
= 0 + (bb
b) e 0 = 0
(4, 4) = r
44
+r
43
r
33
r
34
= bb
b + (bb
a) e b
.
On obtient lautomate represente ` a la gure III.16. Finalement une expres-
1
*
4
*
ab b+(ab+ab a)eb *
bb b+(bb a)eb *
Figure III.16. AFE equivalent apr`es elimination de letat 3.
sion reguli`ere du langage accepte par lautomate de depart est
(ab
b + (ab +ab
a) e b)(bb
b + (bb
a) e b)
.
Puisqu` a toute expression reguli`ere , correspond un automate acceptant
le langage L() et qu` a tout langage L accepte par un automate correspond
une expression reguli`ere telle que L = L(), nous avons le resultat suivant.
Theor`eme III.2.8 (Kleene). Un langage est regulier si et seulement si il
est accepte par un automate ni.
Remarque III.2.9. Dune certaine mani`ere, on peut dire que les expres-
sions reguli`eres sont les generateurs des langages reguliers, alors que les
automates nis en sont les accepteurs.
3. Stabilite de la regularite
Theor`eme III.3.1. Lensemble des langages reguliers est stable par union,
concatenation, etoile de Kleene, image par morphisme, miroir, passage au
complementaire, intersection et shue.
Demonstration. Cela resulte immediatement des resultats demontres au
chapitre II concernant les langages acceptes par automate ni et du theor`eme
de Kleene.
Le resultat suivant est souvent utilise pour verier que certains langages
ne sont pas reguliers. Il sagit simplement dune redite du corollaire I.3.10.
Corollaire III.3.2. Si L est un langage regulier sur =
1
, . . . ,
n
, alors
[L[ = [w[ : w L N est une union nie de progressions arithmetiques.
58 Chapitre III. Langages reguliers et automates
Demonstration. Soit = un alphabet unaire. Lapplication
f :
:
i
, i 1, . . . , n
est un morphisme de monodes preservant les longueurs, i.e., pour tout mot
w
4. Crit`ere de non-regularite
Lemme III.4.1 (Lemme de la pompe).
4
Soit L
un langage regulier.
Il existe un entier tel que pour tout mot w de L satisfaisant [w[ , il
existe x, y, z
z L.
Demonstration. Puisque L est regulier, il est accepte par un AFD / =
(Q, q
0
, F, , ) possedant etats. Un mot w = w
1
w
n
L de longueur n
correspond ` a une execution passant par n + 1 etats q
0
, q
1
, . . . , q
n
,
q
0
w
1
q
1
w
2
q
2
q
n1
wn
q
n
F.
Puisque / poss`ede etats, si n , alors au moins deux etats dans la
suite detats sont egaux. Soient q
i
et q
j
deux tels etats (on suppose que lon
consid`ere la premi`ere repetition de deux etats, i.e., q
i
= q
j
, 0 i < j n
et q
0
, . . . , q
j1
sont deux ` a deux distincts). On a donc pour tout t 0,
lexecution suivante
q
0
w
1
w
i
. .
x
_
_
q
i
w
i+1
w
j
. .
y
_
_
t
q
j
w
j+1
wn
. .
z
q
n
F
o` u []
t
signie que la boucle est empruntee t fois. En posant x, y, z comme
indiques sur la gure III.17, la conclusion en decoule.
Le lemme de la pompe est tr`es souvent utilise pour demontrer que cer-
tains langages ne sont pas reguliers.
Exemple III.4.2. Considerons une fois encore le langage
L = a
n
2
[ n N.
4
En anglais, on trouve souvent lexpression pumping lemma. En fran cais, on ren-
contre parfois, pour des raisons evidentes, la denomination lemme de letoile.
III.4. Crit`ere de non-regularite 59
q q
q =q
y
z x
0
i j
n+1
Figure III.17. Le lemme de la pompe.
Nous avons dej` a montre dans lexemple I.3.13 que ce langage netait pas
regulier (en utilisant la proposition I.3.9). Utilisons ici le lemme de la pompe.
Si L etait regulier, il serait accepte par un AFD / ayant k etats. D`es lors,
le mot a
k
2
est accepte par / et cet automate comprend donc une boucle de
longueur i > 0 (car k
2
k). Par consequent, tout mot de longueur
k
2
+ni, n N
est accepte par /. Or, lensemble des carres parfaits ne contient aucune
progression arithmetique innie. On en tire que le langage L ne peut etre
regulier.
Remarque III.4.3. Attirons lattention du lecteur sur le fait que des lan-
gages non reguliers peuvent neanmoins satisfaire la condition du lemme de la
pompe. En eet, soit L b
est regulier si et seulement si il existe une constante k > 0 telle que pour
tout mot w
,
wv L xy
i
zv L.
Demonstration. La condition est necessaire. Supposons que le langage
L est accepte par un AFD / = (Q, q
0
, F, , ) possedant k etats. Tout mot
w = w
1
w
o` u q
0
est letat initial. Par un raisonnement analogue ` a celui developpe dans
la preuve precedente, il existe 0 i < j tels que q
i
= q
j
et lautomate /
5
Ce resultat est d u ` a J. Jae (SIGACT News, 1978). Nous avons repris ici une preuve
extraite de S. Yu, Regular Languages, Handbook of formal languages, Springer, 1997.
60 Chapitre III. Langages reguliers et automates
a donc une boucle. On pose x = w
1
w
i
, y = w
i+1
w
j
et z = w
j+1
w
et [w[ < k.
Letat initial de / est q
et F = q
w
[ w L. La fonction de transition est
denie par
si [w[ < k 1, alors pour tout ,
(q
w
, ) = q
w
si [w[ = k1, alors pour tout , w est un mot de longueur k et
par hypoth`ese, il peut se decomposer en xyz avec y non vide et tel
que pour tout v
tels que
(q
0
, w
0
) = (q
0
, xz) = q
xz
, avec w
0
= xyz, y ,=
III.5. Exercices 61
et en particulier, w
0
v = w appartient ` a L si et seulement si xzv appartient
` a L. De plus, on a
(q
0
, w
0
v) = (q
0
, xzv) = (q
xz
, v),
ce qui signie que w
0
v = w appartient ` a L(/) si et seulement si xzv appar-
tient ` a L(/) (en eet, on atteint le meme etat de /). Or [xzv[ < n (car y
non vide) et donc, par hypoth`ese de recurrence, xzv appartient ` a L(/) si et
seulement si il appartient ` a L. En conclusion, w L(/) w L.
Remarque III.4.5. Nous voulons faire observer au lecteur que cette derni`ere
proposition necessite une decomposition de w en xyz qui doit pouvoir etre
appliquee pour tout mot wv, v
.
5. Exercices
5.1. Langages reguliers.
Exercice III.5.1. Soit le langage
L = ab
2
a
3
b
4
a
2n1
b
2n
[ n N.
Ce langage est-il regulier ? Justier.
Exercice III.5.2. Le langage a
n
b
n
[ n N est-il regulier ?
Exercice III.5.3. Le langage a
n
b
2n
[ n N est-il regulier ?
Exercice III.5.4. Le langage w a, b
: [w[
a
< [w[
b
est-il regulier ?
Exercice III.5.5. Le langage a
2
n
[ n N est-il regulier ?
Exercice III.5.6. Soit le morphisme f : a, b
a, b tel que
f(a) = b et f(b) = a.
Le langage L = wf(w) [ w a, b
est-il regulier ?
Exercice III.5.7. Soit /un AFD possedant k etats, k 1. Demontrer que
si le langage accepte par / ne contient aucun mot de longueur strictement
inferieure ` a k, alors le langage accepte par / est vide.
Exercice III.5.8. Soit / un AFD possedant k etats, k 1. Demontrer
que si le langage accepte par / est ni, alors tout mot accepte w est tel que
[w[ < k.
Exercice III.5.9. Soit un alphabet de taille au moins 2. Le langage des
palindromes sur est-il regulier ? Que se passe-t-il dans le cas particulier
dun alphabet unaire ?
Exercice III.5.10. Le langage a
n
b
m
a
n+m
[ m, n N est-il regulier ?
62 Chapitre III. Langages reguliers et automates
Exercice III.5.11. Le langage forme des mots sur a, b qui contiennent
deux fois plus de a que de b, i.e.,
L = w a, b
: [w[
a
= 2[w[
b
,
est-il regulier ? Que vaut (L) ?
Exercice III.5.12. Soient les alphabets = a, b, c et = e, f et un
langage L sur . On donne le morphisme h : tel que
h(a) = h(b) = e et h(c) = f.
Si h(L)
[ wu L.
On denit une relation sur
, notee
L
, de la mani`ere suivante. Pour tous
x, y
,
x
L
y x
1
.L = y
1
.L.
En dautres termes, x
L
y si et seulement si pour tout mot w
,
xw L yw L.
Notons que la notation la plus repandue dans la litterature est w
1
L.
Remarque IV.2.2. Avec une telle denition, la formule suivante est alors
immediate (o` u la somme represente lunion),
L =
(
1
.L) +(L), avec (L) =
_
, si L
, sinon.
et J. H. Conway decrireboth Taylors theorem and the mean value theorem.
Proposition IV.2.3. Soit L
un langage. La relation
L
est une
relation dequivalence. Il sagit meme dune congruence
1
` a droite, i.e.,
z
, x
L
y xz
L
yz.
Demonstration. Cest immediat.
[ u
L
w.
Exemple IV.2.5. Soit le langage
L = w a, b
: [w[
a
0 (mod 3).
Pour ce langage, on a par exemple
abbaba
L
aaa car abbaba
1
.L = aaa
1
.L = L
b ,
L
ab car pour u = aa, bu , L et abu L
aba ,
L
bab car pour u = a, abau L et babu , L
a
L
ababaa car a
1
.L = ababaa
1
.L = w a, b
: [w[
a
2 (mod 3).
1
Pour rappel, une congruence est une relation dequivalence qui preserve les operations
de la structure algebrique consideree.
IV.2. Congruence syntaxique 65
En eet, pour w a, b
,
si [w[
a
3
0, alors w
1
.L = u a, b
: [u[
3
0
et [w]
L
= u a, b
: [u[
3
0,
si [w[
a
3
1, alors w
1
.L = u a, b
: [u[
3
2
et [w]
L
= u a, b
: [u[
3
1,
si [w[
a
3
2, alors w
1
.L = u a, b
: [u[
3
1
et [w]
L
= u a, b
: [u[
3
2.
Cet exemple nous montre quen general, w
1
.L ,= [w]
L
.
Denition IV.2.6. Dans le cas dun automate deterministe (ni ou non)
/ = (Q, q
0
, F, , ), par analogie avec la notation w
1
.L, on utilise la nota-
tion suivante. Si q Q est un etat de / et si G Q est un sous-ensemble
detats, on note q
1
.G, lensemble des mots qui sont labels des chemins
debutant en q et aboutissant dans un etat de G, i.e.,
q
1
.G = w
[ (q, w) G.
On denit sur Q une relation dequivalence comme suit : si p, q Q, alors
p
A
q p
1
.F = q
1
.F.
Remarque IV.2.7. Avec la notation que nous venons dintroduire, le lan-
gage accepte par lautomate deterministe / = (Q, q
0
, F, , ) est simplement
q
1
0
.F.
Lemme IV.2.8. Soit / = (Q, q
0
, F, , ) un automate deterministe ac-
ceptant un langage L. Si q Q et w
[ (q, u) F.
Or (q
0
, w) = q. Ainsi, pour tout u q
1
.F, on a
(q
0
, wu) = ((q
0
, w), u) = (q, u) F
et donc wu appartient ` a L(/) = L, cest-` a-dire, u appartient ` a w
1
.L et
reciproquement.
w
q
F
u
q
0
Figure IV.2. q
1
.F = w
1
.L si (q
0
, w) = q.
66 Chapitre IV. Automate minimal
L pour
1
.L. La raison en est
simple, il est clair que
D
(L +M) = D
L +D
M
et
D
(LM) = (D
L) M +(L) D
M
o` u, une fois encore, somme et produit representent respectivement lunion
et la concatenation.
3. Automate minimal
Nous allons tirer parti de la congruence de Nerode introduite ` a la section
precedente pour denir un automate particulier, ` a savoir lautomate mini-
mal du langage L. La denition peut ` a premi`ere vue sembler articielle,
mais nous allons montrer quainsi introduit, lautomate minimal jouit de
proprietes fort interessantes.
Denition IV.3.1. On denit lautomate minimal
/
L
= (Q
L
, q
0,L
, F
L
, ,
L
)
dun langage L
comme suit :
Q
L
= w
1
.L [ w
,
q
0,L
=
1
.L = L,
F
L
= w
1
.L [ w L = q Q
L
[ q,
L
(q, ) =
1
.q, pour tous q Q
L
, .
Gr ace au lemme IV.2.9, la fonction de transition de lautomate setend ` a
Q
L
par
L
(q, w) = w
1
.q , q Q
L
, w
.
Nous devons verier que cette denition a un sens en montrant que la
fonction de transition ne depend pas du representant choisi. Ainsi, si un
etat de /
L
est de la forme x
1
.L = y
1
.L (x, y
), alors x
L
y.
2
cf. J. A. Brzozowski, Derivatives of regular expressions, J. of the Assoc. for Comp.
Machinery 11 (1964), 481494.
IV.3. Automate minimal 67
Puisque
L
est une congruence ` a droite, pour tout , x
L
y et
donc (x)
1
.L = (y)
1
.L. En appliquant le lemme IV.2.9, on trouve bien
1
.(x
1
.L) =
1
.(y
1
.L).
Remarque IV.3.2. Au vu de la denition de
L
, il est clair que lensemble
des etats de /, w
1
.L [ w
/
L
= [w]
L
[ w
L
correspond un etat w
1
.L de lautomate minimal /
L
et reciproquement.
Cest pour cette raison que, dans la litterature, on trouve egalement une
denition de lautomate minimal en termes des classes dequivalence de
L
.
Ainsi, on aurait pu denir lautomate minimal comme suit :
Q
L
= [w]
L
[ w
q
0,L
= []
L
F
L
= [w]
L
[ w L
L
([w]
L
, ) = [w]
L
.
Cette derni`ere denition est equivalente ` a celle donnee en IV.3.1 car si [w]
L
correspond ` a w
1
.L, alors [w]
L
correspond ` a (w)
1
.L =
1
.(w
1
.L).
Dans la suite, nous utiliserons principalement la denition de lautomate
minimal donnee en IV.3.1.
Remarquons encore que si x
L
y, alors
L
(q
0,L
, x) =
L
(q
0,L
, y)
car il sut de se rappeler que q
0,L
= L et d`es lors, il vient
L
(q
0,L
, x) = x
1
.L = y
1
.L =
L
(q
0,L
, y).
Exemple IV.3.3. Poursuivons lexemple IV.2.5. Il est facile de voir que
pour le langage L forme des mots sur a, b contenant un nombre de a
multiple de trois, la congruence de Nerode poss`ede trois classes dequivalence
[]
L
, [a]
L
et [aa]
L
.
Dit autrement, lautomate minimal /
L
a trois etats
1
.L, a
1
.L et aa
1
.L.
Pour denir la fonction de transition, on a
L
(
1
.L, a) = a
1
.(
1
.L) = a
1
.L
L
(
1
.L, b) = b
1
.(
1
.L) = b
1
.L =
1
.L car
L
b
L
(a
1
.L, a) = a
1
.(a
1
.L) = aa
1
.L
L
(a
1
.L, b) = b
1
.(a
1
.L) = ab
1
.L = a
1
.L car a
L
ab
L
(aa
1
.L, a) = a
1
.(aa
1
.L) = aaa
1
.L =
1
.L car
L
aaa
L
(aa
1
.L, b) = b
1
.(aa
1
.L) = aab
1
.L = aa
1
.L car aa
L
aab.
Si on note 1, 2, 3 les trois langages
1
.L = L, a
1
.L, aa
1
.L, on obtient
lautomate represente ` a la gure IV.3.
68 Chapitre IV. Automate minimal
a
a
a
b
b
b
1 2
3
Figure IV.3. Un automate minimal.
Remarque IV.3.4. On observe que, dans la denition de /
L
, les etats de
lautomate minimal de L sont des ensembles de mots. Dans lexemple prece-
dent, on a un nombre ni detats et chaque etat correspond ` a un ensemble
inni de mots.
Exemple IV.3.5. Considerons le langage L forme des mots sur a, b ayant
meme nombre de a que de b, i.e.,
L = w a, b
: [w[
a
= [w[
b
.
Une application immediate du lemme de la pompe montre que ce langage
nest pas regulier. On peut neanmoins rechercher son automate minimal
puisque la relation
L
est denie pour tout langage L. On saper coit que
le nombre de classes dequivalence pour la relation
L
est inni. En eet,
pour tout n Z,
c
n
:= [a
i
b
j
]
L
, avec i j = n
est une classe dequivalence et il est clair que si m ,= n, alors c
m
,= c
n
. De
plus,
L
((a
i
b
j
)
1
.L, a) = (a
i+1
b
j
)
1
.L = (a
i
b
j1
)
1
.L
et
L
((a
i
b
j
)
1
.L, b) = (a
i
b
j+1
)
1
.L = (a
i1
b
j
)
1
.L.
(Dans les expressions ci-dessus, on ne consid`ere que les expressions pour
lesquelles les exposants sont positifs ou nuls.) Le seul etat nal de lautomate
est (a
i
b
i
)
1
.L = L. Lautomate minimal de L est represente ` a la gure IV.4.
a
b
a
b
a
a
b b
Figure IV.4. Lautomate minimal dun langage non regulier.
On peut dores-et-dej` a remarquer que pour ce langage non regulier, le
nombre detats de lautomate minimal est inni.
IV.3. Automate minimal 69
Proposition IV.3.6. Lautomate minimal dun langage L
accepte L.
Demonstration. En eet, soit w
,
w L(/
L
)
L
(q
0,L
, w) F
L
w
1
.L F
L
w L.
On a utilise le fait que
L
(q
0,L
, w) =
L
(
1
.L, w) = w
1
.(
1
.L) = (w)
1
.L.
tel que (q
0
, w) = q.
Un automate deterministe / = (Q, q
0
, F, , ) est reduit si pour tous
p, q Q,
p
1
.F = q
1
.F entrane p = q.
En dautres termes, un AFD est reduit, si les langages acceptes depuis deux
etats distincts sont distincts ou encore si chaque classe dequivalence pour
la relation
A
sur Q est un singleton.
Le resultat suivant justie lappellation minimal.
Theor`eme IV.3.8. Soient L
un langage et /
L
= (Q
L
, q
0,L
, F
L
, ,
L
)
son automate minimal. Si B = (Q, q
0
, F, , ) est un automate accessible et
deterministe acceptant L, alors il existe une application : Q Q
L
telle
que
est surjectif,
(q
0
) = q
0,L
,
, q Q : ((q, )) =
L
((q), ),
(F) = F
L
.
a a
b
b
a
b
a
a,b
a
b
b
b
a a
b
a,b
Figure IV.5. Une application satisfaisant les proprietes
du theor`eme IV.3.8.
70 Chapitre IV. Automate minimal
Demonstration. Puisque B est accessible, pour tout etat q Q, il exis-
te un mot w
tel que (q
0
, w) = q. Supposons tout dabord quune
application satisfaisant les proprietes enoncees existe. Dans ce cas
3
, On eectue
dabord
lanalyse.
(q) = ((q
0
, w)) =
L
((q
0
), w) =
L
(q
0,L
, w) = w
1
.L = q
1
.F
o` u pour la derni`ere egalite, on a applique le lemme IV.2.8. Montrons ` a
present que lapplication Passons ` a la
synth`ese.
: Q Q
L
: q q
1
.F
poss`ede les proprietes indiquees :
il est clair que est ` a valeurs dans Q
L
car B etant accessible, il
est toujours possible decrire q
1
.F sous la forme w
1
.L pour un
certain w
.
On a (q
0
) = q
1
0
.F = L = q
0,L
.
Soient et q Q. Par denition de , on a tout dabord
((q, )) = ((q, ))
1
.F
Si w
3
En particulier, ceci prouve que si une telle application existe, alors elle est unique.
IV.3. Automate minimal 71
Proposition IV.3.10. Soit L
un langage.
(i) Lautomate minimal /
L
= (Q
L
, q
0,L
, F
L
, ,
L
) de L est accessible
et reduit.
(ii) Soit B = (Q, q
0
, F, , ) un automate deterministe accessible ac-
ceptant L. Cet automate est reduit si et seulement si lapplication
: Q Q
L
denie au theor`eme IV.3.8 est une bijection. Dans ce
cas, les automates /
L
et B sont isomorphes.
Demonstration. Lautomate minimal est accessible car un etat quel-
conque de /
L
est de la forme w
1
.L pour un mot w
et
L
(q
0,L
, w) = w
1
.L.
Par denition de lensemble detats Q
L
, il est clair que /
L
est reduit.
Si B est un automate accessible, lapplication : Q Q
L
introduite au
theor`eme IV.3.8 est surjective. Cette application est injective si et seulement
si pour tous p, q Q,
(p) = (q) p = q
ce qui se reecrit
p
1
.F = q
1
.F p = q
et qui signie que B est reduit.
tel que
(p, w) F et (q, w) , F
ou
(p, w) , F et (q, w) F.
On dit alors quun tel mot distingue les etats p et q ou encore que le couple
(p, q) est distingue. Dans lalgorithme qui suit, on notera ^
lensemble des
couples detats qui sont distingues par un mot de longueur et qui ne sont
distingues par aucun mot plus court.
Algorithme de recherche des etats equivalents
(1) Initialisation : lors de cette etape, on determine les couples detats
distingues par le mot vide (seul mot de longueur = 0).
On pose := 0.
Pour tout p F et tout q QF, la paire (p, q) est distinguee car le
mot vide appartient ` a p
1
.F mais pas ` a q
1
.F. Soit ^
0
lensemble
de ces paires.
(2) Incrementation : on determine les couples detats distingues par un mot
de longueur + 1 et non distingues par un mot de longueur .
Si ^
= , lalgorithme sach`eve
4
.
4
On doit remarquer que si N
= et N
+1
= .
Il existe donc (r, s) N
+1
distingue par un mot w de longueur + 1. D`es lors, le mot
w de longueur distingue les etats (r, ) = r
et (s, ) = s
. Puisque N
= , on en
conclut que r
et s
. Sil existe
tel que
(r, ) = p et (s, ) = q
ou
(s, ) = p et (r, ) = q,
alors la paire (r, s) est distinguee par un mot de longueur + 1.
Soit ^
+1
lensemble de ces paires.
Remplacer par + 1 et repeter (2).
Exemple IV.4.1. Appliquons lalgorithme precedent ` a lAFD represente
` a la gure IV.6.
a
a
b
b
a b
b
b
b
a
a
a
5 6
3 2 1
4
Figure IV.6. Un AFD dont on recherche les etats equiva-
lents pour
A
.
La premi`ere etape donne le tableau suivant. Dans ce tableau, on denote
simplement par i lappartenance dun couple ` a lensemble ^
i
, i N. De
plus, par raison de symetrie, on sinteressera uniquement ` a la partie situee
au dessus de la diagonale principale.
1 2 3 4 5 6
1 0 0
2 0 0 0
3 0
4 0
5 0
6
Puisque (1.a, 3.a) = (2, 6), (1.b, 6.b) = (1, 2), (3.a, 4.a) = (6, 5) et (4, 6) =
(5, 6), on a, ` a la deuxi`eme etape, le tableau ci-dessous.
1 2 3 4 5 6
1 0 1 0 1
2 0 0 0
3 1 0
4 0 1
5 0
6
74 Chapitre IV. Automate minimal
Lalgorithme sach`eve car (1.a, 4.a) = (2, 5), (1.b, 4.b) = (1, 1), (2.a, 5.a) =
(1, 4), (2.b, 5.b) = (3, 6), (3.a, 6.a) = (6, 6) et (3.b, 6.b) = (2, 2). On en
conclut que 1
A
4, 2
A
5 et 3
A
6.
Puisque nous pouvons supposer avoir un AFD / accessible, le theor`eme
IV.3.8 nous arme que lautomate / se projette au moyen de lapplication
sur lautomate minimal du langage L accepte par / et que des etats de /
equivalents pour
A
sont envoyes sur un meme etat de /
L
. Ainsi, les etats
de /
L
vont correspondre aux classes dequivalence de
A
.
Toujours en vertu du theor`eme IV.3.8, les transitions de lautomate mi-
nimal sont denies par
L
((q), ) = ((q, ))
si (resp.
L
) est la fonction de transition de / (resp. /
L
). Traduit en
termes detats equivalents, cela signie que si un etat de /
L
correspond ` a
une classe dequivalence [q]
A
pour la relation
A
, alors la lecture de depuis
cet etat dans /
L
conduit ` a letat correspondant ` a la classe [q.]
A
.
Exemple IV.4.2. Si nous continuons lexemple precedent, on a [1]
A
=
1, 4, [2]
A
= 2, 5 et [3]
A
= 3, 6. Puisque dans lautomate de depart,
1.a = 2 et 1.b = 1, on a
L
((1), a) = (2) et
L
((1), b) = (1). Ceci
signie que, dans lautomate minimal, la lecture de a (resp. b) depuis letat
correspondant ` a 1, 4 conduit ` a [2]
A
= 2, 5 (resp. [1]
A
= 1, 4). En
continuant de la sorte, on obtient lautomate de la gure IV.7.
b
a b
a
b
a
{2,5} {1,4} {3,6}
Figure IV.7. Un automate minimal.
Exemple IV.4.3. Soit lAFD accessible / represente ` a la gure IV.8.
Nous allons lui appliquer lalgorithme de recherche des etats equivalents pour
1
b
a
2
a
b
3
b
a
4
b
a
Figure IV.8. Un AFD accessible /.
IV.4. Construction de lautomate minimal 75
montrer quil est reduit (et quil sagit donc dun automate minimal puisquil
est visiblement accessible). Avec les memes notations que precedemment,
on obtient rapidement le tableau suivant.
1 2 3 4
1 0 0 1
2 1 0
3 0
4
4.1. Une autre procedure de minimisation.
Proposition IV.4.4. Soit / un AFD acceptant un langage L. Si pour tout
automate B, (B) designe lautomate deterministe equivalent ` a B
R
obtenu
par construction des sous-ensembles detats, alors ((/)) est lautomate
minimal de L.
Demonstration. Si B est un AFD acceptant M, il est clair que (B) ac-
cepte M
R
et quil est accessible. En eet, dans la procedure de construction
par sous-ensembles, on ne consid`ere que les etats accessibles car on recherche
de proche en proche les etats atteints depuis letat initial. Il sut d`es lors de
montrer que si B est un AFD accessible acceptant un langage M, alors (B)
est un AFD accessible et reduit acceptant M
R
. Dans ce cas, (/) sera un
AFD accessible acceptant L
R
et ((/)) sera un AFD accessible et reduit
acceptant (L
R
)
R
= L. On conclut alors par la proposition IV.3.10.
Soit B un AFD accessible. Montrons que (B) est reduit. Soient P, Q
deux etats de (B). Supposons que P
1
.T = Q
1
.T (o` u T designe lensemble
des etats nals de (B)). De par la construction par sous-ensembles, letat
P (resp. Q) est constitue detats
5
p
1
, . . . , p
r
(resp. q
1
, . . . , q
s
) de B
R
et un
etat est nal sil est un sous-ensemble detats de B
R
contenant un etat nal
de B
R
(donc ici contenant letat initial q
0
de B, i.e., lunique etat nal de
B
R
).
Si w appartient ` a P
1
.T, cela signie que, dans (B), w est le label dun
chemin debutant dans P et aboutissant dans un etat nal. Encore un fois,
de par la construction par sous-ensembles, cela signie que dans B
R
on a un
chemin de label w debutant dans un des etats p
i
et aboutissant dans q
0
. Ou
de mani`ere equivalente, dans B, w
R
est le label dun chemin debutant dans
q
0
et aboutissant dans p
i
. Reciproquement, pour tout i 1, . . . , r, si w
est label dun chemin dans B debutant dans q
0
et aboutissant dans p
i
, alors
dans (B), w
R
appartient ` a P
1
.F. Autrement dit, on a
P
1
.T = (q
1
0
.p
1
, . . . , p
r
)
R
o` u dans le membre de gauche (resp. de droite), on consid`ere lautomate
(B) (resp. B).
Dans B, pour tout i 1, . . . , r, si q
0
.w = p
i
, cela signie quil appar-
tient ` a q
1
0
.p
1
, . . . , p
r
et puisque nous avons supposer que P
1
.T = Q
1
.T,
5
Les automates B et B
R
ont le meme ensemble detats.
76 Chapitre IV. Automate minimal
on en deduit que w appartient ` a q
1
0
.q
1
, . . . , q
s
. Il existe j 1, . . . , s tel
que, dans B, q
0
.w = p
j
. Or puisque B est deterministe, on trouve p
i
= q
j
et
P Q. On proc`ede de meme pour lautre inclusion et ainsi, P = Q.
un morphisme de monodes. Si
M
. On a
w
1
.f
1
(M) = u
[ wu f
1
(M)
= u
[ f(wu) M
= u
[ f(w)f(u) M
= u
[ f(u) f(w)
1
.M
= f
1
(f(w)
1
.M)
Or M est regulier donc son automate minimal est ni et f(w)
1
.M ne peut
prendre quun nombre ni de valeurs. On en conclut que, quel que soit
w
, w
1
.f
1
(M) ne peut prendre quun nombre ni de valeurs. Ainsi,
lautomate minimal du langage f
1
.M est ni.
b)))).
On pourra comparer ce resultat avec le theor`eme de representation de Chomsky-
Sch utzenberger pour les langages algebriques (cf. theor`eme VI.10.3).
Ce resultat nest pas
nouveau! Mais la preuve
est elegante.
Proposition IV.5.3. Si L
. Il vient
w
1
.Pref(L) = u
[ wu Pref(L)
= u
[ v
: wuv L
= u
[ v
: uv w
1
.L
= Pref(w
1
.L).
Le langage L etant regulier, w
1
.L ne peut prendre quun nombre ni de
valeurs. Par consequent, Pref(w
1
.L) ne prend aussi quun nombre ni de
valeurs et lensemble
Pref(w
1
.L) [ w
est ni.
6
Voir par exemple, le Handbook of formal languages, vol. 1, pour des references.
IV.5. Applications 79
Corollaire IV.5.4. Si L
par
k
L = u
[ u
k
L.
Exemple IV.5.7. Soit L = a
L = a
.
On dispose du resultat suivant.
Proposition IV.5.8. Si L
L est aussi
un langage regulier.
An de demontrer ce resultat, nous avons besoin du lemme suivant.
Lemme IV.5.9. Soit L un langage regulier. Si p est un etat de lautomate
minimal de L donne dans la denition IV.3.1 alors p et
S(p) = w
[ p = w
1
.L
sont deux langages reguliers.
Demonstration. Puisque p est un etat de lautomate minimal /
L
=
(Q
L
, q
0,L
, F
L
, ,
L
), il existe w
tel que p = w
1
.L. En dautres termes,
p = u
[ wu L = u
[
L
(q
0,L
, wu) F
L
. Il vient
u
1
.S(p) = v
[ uv S(p)
= v
[ p = (uv)
1
.L
= v
[ p = v
1
.(u
1
.L).
Or L est regulier, son automate minimal est donc ni et u
1
.L ne peut
prendre quun nombre ni de valeurs distinctes. Par consequent,
u
1
.S(p) [ u
L =
_
pQ
L
(S(p)
k
p).
Si u appartient ` a
k+1
p avec p Q
L
. De plus, par denition meme
de S(p), u appartient egalement ` a ce dernier ensemble.
Demontrons lautre inclusion. Si u appartient au membre de droite, cela
signie que p secrit u
1
.L et que u
k
appartient ` a p. Par consequent, u
k
appartient ` a u
1
.L et donc u
k+1
appartient ` a L.
Pour conclure la preuve, on proc`ede par recurrence sur k. Si k = 1,
alors par hypoth`ese
1
L lest encore. Au
vu du lemme precedent, pour tout etat p Q
L
, p et S(p) sont reguliers.
Par hypoth`ese de recurrence,
k
p est regulier
car il sagit de lintersection de deux langages reguliers. La formule donnee
ci-dessus ne fait ainsi intervenir quune union nie de langages reguliers (en
eet, L est regulier et donc, Q
L
est ni). Par consequent,
k+1
L est regulier.
ba(bb)
,
(a +b)
aba(a +b)
,
(ab +ba)
,
le langage forme des mots contenant le facteur aa ou bb,
le langage forme des mots contenant le facteur aa et bb,
(aab)
(ba)
,
le langage forme des mots de (aab)
(ba)
.
82 Chapitre IV. Automate minimal
1
a
b
2
a b
3
b
4
a,b
5
a
6
a
7
b
a
b
b
a
Figure IV.15. Un autre AFD.
En deduire lautomate minimal de L.
Exercice IV.6.4. Montrer que
L
nest en general pas une congruence ` a
gauche, i.e., il existe z
tel que x
L
y et zx ,
L
zy.
Exercice IV.6.5. Soit L = ab, aab, aba, ba, bb, aaa. Quels sont les dif-
ferents ensembles de la forme
w
1
.L, w a, b
.
En deduire lautomate minimal de L.
Exercice IV.6.6. Soit L = (a + b)
.
En deduire lautomate minimal de L.
Exercice IV.6.7. Soit L, le langage sur a, b des mots contenant exacte-
ment deux a. Quels sont les dierents ensembles de la forme
w
1
.L, w a, b
.
En deduire lautomate minimal de L.
Exercice IV.6.8. Soit lautomate deterministe / represente ` a la gure
IV.16. Rechercher lautomate minimal du langage accepte par /. On
procedera par deux methodes : la recherche des etats equivalents et la proce-
dure ((/)).
Exercice IV.6.9. Soit le langage
L = a
n
b
m
[ n, m N : n m.
Caracteriser les etats de lautomate minimal de L et donner la table de
transition de cet automate.
IV.6. Exercices 83
a
b
a
b
a
b
a
b
b
b
a
a,b
a
b
a
b
a
Figure IV.16. Un autre AFD dont on cherche le minimal.
Exercice IV.6.10. Soit lautomate ni deterministe / represente ` a la g-
ure IV.17. Rechercher les etats equivalents pour la relation
A
. En deduire
a
b
b
a
a,b
a
a
b
b
Figure IV.17. Recherche des etats equivalents.
lautomate minimal du langage accepte par /.
Exercice IV.6.11. On consid`ere lalphabet = a, b, c.
Donner lautomate minimal du langage L = a
(dans votre
reponse, justier en quoi lautomate que vous proposez est mini-
mal).
Quelles sont les classes dequivalence de
pour la relation de
Nerode
L
et quels sont les dierents ensembles de la forme w
1
.L,
w
?
La cl oture commutative de L donnee par
com(L) = w
[ v L, : [w[
= [v[
, w
i
, le transducteur T associe un mot de sortie
T (w)
donne par
(q
0
, w
1
) ((q
0
, w
1
), w
2
) ((q
0
, w
1
w
2
), w
3
) ((q
0
, w
1
w
1
), w
).
La representation sagitale dun transducteur se fait de la fa con suivante.
Pour tous q, q
Q, , si (q, ) = q
et (q, ) = u
, alors on note
q
/u
q
.
Exemple V.1.2. Voici un exemple de transducteur. Ici, = a, b,
1 2
a/a
b/bc
b/b
a/a
Figure V.1. Un transducteur.
lalphabet de sortie est = a, b, c et la fonction de sortie est denie
par (1, a) = a, (1, b) = b, (2, a) = a et (2, b) = bc. Considerant le mot
w = bab, on a
1
b/b
1
a/a
2
b/bc
1
et donc T (w) = babc. Il est facile de voir que ce transducteur ins`ere un c
apr`es chaque occurrence de ab dans le mot dentree.
Remarque V.1.3. La fonction sur
et ` a valeurs dans
, denie par le
transducteur T , est souvent appelee fonction rationnelle.
85
86 Chapitre V. Quelques complements sur les langages reguliers
Exemple V.1.4. Si f :
dans
est regulier.
Demonstration.
1
Soient / = (Q, q
0
, F, , ) un AFD acceptant L et
T = (Q
, q
0
, ,
, q
0
, F
, ,
()0, 1, . . . , k o` u k = max
,q
Q
[(q
, )[,
q
0
= (q
0
, q
0
, , 0),
la relation de transition
, , 0), , (q, q
, , 0))
.
Si (q
, ) = y
1
y
j
, alors pour tout i tel que 1 i j
((q, q
, , i 1), y
i
, (q, q
, , i))
et
((q, q
, , j), , ((q, ),
(q
, ), , 0))
.
1
La preuve presentee ici est issue de : J.-P. Allouche, J. Shallit, Automatic Sequences,
Theory, Applications, Generalizations, Cambridge University Press (2003).
V.1. Transduction 87
En particulier, si (q
, ) = alors
((q, q
, , 0), , ((q, ),
(q
, ), , 0))
.
Enn, F = (q, q
, , 0) : q F.
Lidee ` a la base de cette denition est la suivante : si w T (L), il existe
x L tel que w = T (x). Supposons que x = x
1
x
r
, x
t
, et que w
t
est utilisee
pour memoriser la lettre = x
t
du mot x qui vient detre supposee. La
quatri`eme composante permet de savoir combien de lettres de w
t
ont dej` a
ete rencontrees. Cette derni`ere composante sert de compteur, initialise ` a
zero et incremente dune unite ` a chaque fois quune lettre de w
t
est lue.
Lorsque ce compteur atteint [w
t
[, on utilise une -transition pour reinitialiser
la troisi`eme composante ` a et la quatri`eme ` a 0. De plus, pour simuler
le comportement de / et T , la premi`ere composante passe ` a (q, ) et la
deuxi`eme ` a
(q
0
= p
0
x
1
/w
1
p
1
x
2
/w
2
p
2
xr/wr
p
r
.
On note w
t
= w
t1
w
tkt
. Ainsi, dans B, la lecture de w peut conduire ` a la
suite detats
(p
0
, p
0
, , 0)
. .
=q
(p
0
, p
0
, x
1
, 0)
w
11
(p
0
, p
0
, x
1
, 1)
w
1k
1
(p
0
, p
0
, x
1
, k
1
)
((p
0
, x
1
),
(p
0
, x
1
), , 0)
. .
=(p
1
,p
1
,,0)
(p
1
, p
1
, x
2
, 0)
w
21
w
2k
2
(p
1
, p
1
, x
2
, k
2
)
(p
2
, p
2
, , 0)
(p
2
, p
2
, x
3
, 0)
.
.
.
(p
r1
, p
r1
, , 0)
(p
r1
, p
r1
, x
r
, 0)
w
r1
w
rkr
(p
r1
, p
r1
, x
r
, k
r
)
(p
r
, p
r
, , 0) F
.
Ceci prouve que le mot w = w
11
w
1k
1
w
21
w
2k
2
w
r1
w
rkr
est ac-
cepte par B. Pour lautre inclusion, si w L(B), alors cela signie que
partant de letat initial q
0
, on dispose dun chemin conduisant ` a un etat
88 Chapitre V. Quelques complements sur les langages reguliers
nal de F
[ T (x) L
est regulier.
Demonstration. Il est aise de construire un AFD acceptant T
1
(L) ` a
partir dun AFD / = (Q, q
0
, F, , ) acceptant L et du transducteur T =
(Q
, q
0
, ,
, q
0
, F
, ,
)
deni par
Q
= Q
Q,
q
0
= (q
0
, q
0
),
F
= Q
F et
pour tout ,
((q
, q), ) = (
(q
, ), (q, (q
, ))).
La premi`ere composante simule le transducteur T et la seconde composante
simule lautomate / sur la sortie produite par T . Ainsi, il est clair que
L(B) = T
1
(L).
u.
Pour ce faire, nous allons decrire lautomate minimal de ce langage. Les
etats sont de la forme w
1
.L avec w
. Ainsi,
v w
1
.L wv
u.
Pour decrire les ensembles w
1
.L, il est utile dintroduire, pour tout prexe
p de u, lensemble
E
u
(p) =
: p =
, u =
u.
Exemple V.2.1. Avec les notations precedentes, si
w = aabbab et u = babbaab,
alors
aabbab
. .
w
baab et aabbab
. .
w
abbaab
appartiennent ` a L =
u. Ici,
w,u
= bab car
u = bab baab
w = aab bab
.
De plus, on a
E
u
(
w,u
) = baab, abbaab, u
En eet, les suxes de
w,u
sont , b, ab, bab. Parmi eux, bab et b sont
prexes de u et on a les factorisations suivantes,
u =
..
bab
..
w,u
baab et u =
..
ba
..
b
. .
w,u
abbaab.
90 Chapitre V. Quelques complements sur les langages reguliers
Ainsi, on se convainc aisement que
w
1
.L = L E
u
(
w,u
).
Si u = u
1
u
= u
1
u
.
Les etats de lautomate minimal de L sont donc les
L E
u
(p
i
), i 0, . . . , .
Au vu de ce qui prec`ede, il est clair que
L E
u
(p
i
) = p
1
i
.L.
Si on se rappelle la denition de lautomate minimal dun langage, on retrouve
les caracteristiques de celui-ci.
Letat initial est tel que
p
1
i
.L = L,
et donc i = 0. En eet, si 0 < i , p
1
i
.L contient au moins un
mot de longueur strictement inferieure ` a [u[, alors que L ne contient
que des mots de longueur au moins [u[.
Un etat est nal si et seulement si p
1
i
.L. Donc, le seul etat
nal est p
1
.L.
Recherchons la fonction de transition de lautomate. Si ,
alors par denition de
L
, on a
L
(p
1
i
.L, ) = (p
i
)
1
.L.
De plus, si = u
i+1
, alors p
i
= p
i+1
. Sinon, ,= u
i+1
et
(p
i
)
1
.L = p
1
j
.L
o` u p
j
est le plus grand prexe de u qui soit suxe de p
i
. (Deni-
tion somme toute assez naturelle au vu de la dention des ensembles
E
u
(p).)
Ainsi, pour un mot u donne, il est facile de construire la table de
lautomate. Nous convenons de noter i letat correspondant ` a p
1
i
.L.
Exemple V.2.2. Soit u = abbab. On a
i p
i
(i, a) (i, b)
0 1 car a = p
1
0 car p
0
suxe de b
1 a 1 car p
1
suxe de aa 2 car ab = p
2
2 ab 1 car p
1
suxe de aba 3 car abb = p
3
3 abb 4 car abba = p
4
0 car p
0
suxe de abbb
4 abba 1 car p
1
suxe de abbaa 5 car abbab = p
5
5 abbab 1 car p
1
suxe de abbaba 3 car p
3
suxe de abbabb
et on trouve lautomate represente ` a la gure V.4. Si on doit ecrire un
programme detectant la premi`ere occurrence de abbab dans un texte fourni
en entree, il sut de decreter que la procedure sarrete une fois letat 5
V.2. Recherche dun mot dans un texte 91
b
0 1 2 3 4 5
a
b
a
b
a b b a
b a
b
Figure V.4. Un automate detectant abbab.
atteint. Si on devait compter le nombre doccurrence du facteur abbab dans
un texte donne, on pourrait decider dincrementer un compteur dune unite
` a chaque fois que letat 5 serait atteint.
Remarque V.2.3. La construction de la table de transition de lautomate
seectue en un temps proportionnel ` a [u[. En eet, le nombre detats est
[u[+1 et pour chaque etat et chaque lettre de lalphabet, une seule operation
de comparaison de mots est necessaire pour determiner letat atteint. Une
fois la table de transition construite, la recherche dun mot dans un texte
T prend un temps proportionnel ` a [T[ puisque le texte T est lu lettre par
lettre dans lautomate.
Exemple V.2.4. En appliquant la construction detaillee dans cette sec-
tion, on peut construire aisement un automate reconnaissant la sequence
genetique agata. Cet automate est represente ` a la gure V.5. De meme,
a
a
a
a
c
g
g
g,c,t
c,t
g,c,t
c,t
a
g
t a
g,c,t
agata
Figure V.5. Un automate detectant agata.
pour rechercher le mot ananas dans un texte, on a lautomate de la gure
V.6. Sur cette derni`ere, toutes les transitions non representees aboutissent
` a letat initial, lalphabet etant a, b, . . . , z.
92 Chapitre V. Quelques complements sur les langages reguliers
s a n a n a
a
a
n
Figure V.6. Un automate detectant ananas.
3. Fonction de complexite dun langage regulier
Denition V.3.1. Soit L
L
: N N : n #(L
n
).
Cette fonction associe donc ` a n le nombre de mots de longueur n dans le
langage L.
Le but de cette section est detudier la fonction de complexite dun lan-
gage regulier. Le resultat principal est que la suite (
L
(n))
nN
satisfait une
relation de recurrence lineaire ` a coecients constants.
Soit L
sQ
[M
n
]
q,s
M
s,r
.
Par hypoth`ese de recurrence, [M
n
]
q,s
compte le nombre de chemins de
longueur n joignant q ` a s. Or, il est clair que le nombre de chemins de
longueur n + 1 joignant q ` a r sobtient ` a partir des chemins de longueur n
joignant q et s et des chemins de longueur 1 joignant s ` a r.
q
s
r
n
1
Figure V.8. Chemins de longueur n + 1 joignant q ` a r.
L
(n) =
fF
[M
n
]
q
0
,f
.
Demonstration. Cest evident.
L
(n) = c
1
L
(n 1) + +c
k
L
(n k), n k.
Le probl`eme revient ` a reussir ` a exprimer
L
(n) sous la forme dune for-
mule close. Cette question ` a propos des suites lineaires recurrentes est en
toute generalite dicile ` a resoudre. On dispose du resultat suivant que nous
donnons ici sans demonstration.
Proposition V.3.7. Soit k 1.Si une suite (u
n
)
nN
satisfait une relation
de recurrence lineaire ` a coecients constants de la forme
u
n
= c
1
u
n1
+ +c
k
u
nk
, n k
et si
1
, . . . ,
r
sont les racines de multiplicite m
1
, . . . , m
r
du polyn ome ca-
racteristique de la recurrence
X
k
c
1
X
k1
c
k
,
alors il existe des polyn omes P
i
de degre strictement inferieur ` a m
i
,
i 1, . . . , r, tels que
u
n
= P
1
(n)
n
1
+ +P
r
(n)
n
r
.
En particulier, les polyn omes P
1
, . . . , P
r
sont enti`erement determines par les
conditions initiales u
0
, . . . , u
k1
.
Ainsi, ce theor`eme nous montre que rechercher une forme close pour
L
(n) revient ` a rechercher les racines dun polyn ome de degre k.
Exemple V.3.8. Poursuivons lexemple V.3.3. Le polyn ome caracteris-
tique de la matrice dadjacence est donne par
det
_
_
1 1 0
1 1
0 0 2
_
_
= (2 )(
2
1).
Ainsi, puisque
(2 )(
2
1) =
3
+ 3
2
2,
V.3. Fonction de complexite dun langage regulier 95
en vertu du theor`eme de Cayley-Hamilton, on a
M
3
= 3M
2
M 2I
et donc pour tout n 3,
M
n
= 3M
n1
M
n2
2M
n3
.
En consequence du corollaire V.3.5, on a
L
(n) = 3
L
(n 1)
L
(n 2) 2
L
(n 3), n 3.
De plus,
L
(0) = 1,
L
(1) = 2 et
L
(2) = 3
car , a, b, ab, ba, bb appartiennent ` a L. Pour determiner une formule close
pour
L
(n), nous factorisons tout dabord le polyn ome caracteristique de la
relation de recurrence,
X
3
3X
2
+X + 2 = (X 2)(X
1 +
5
2
)(X
1
5
2
).
En vertu de la proposition V.3.7, puisque les trois racines du polyn ome sont
simples, il existe trois constantes A, B, C telles que
L
(n) = A2
n
+B
_
1 +
5
2
_
n
+C
_
1
5
2
_
n
, n 3.
Au vu des conditions initiales, on a le syst`eme suivant
_
_
1 = A +B +C
2 = 2A +B
_
1+
5
2
_
+C
_
1
5
2
_
3 = 4A +B
_
1+
5
2
_
2
+C
_
1
5
2
_
2
et on trouve
A = 0, B =
5 + 3
5
10
et C =
5 3
5
10
.
Par consequent,
(4)
L
(n) =
5 + 3
5
10
_
1 +
5
2
_
n
+
5 3
5
10
_
1
5
2
_
n
.
Remarque V.3.9. La presence dun puits, ou plus generalement dun etat
non coaccessible (i.e., depuis lequel on ne peut atteindre aucun etat nal),
na pas dinuence sur le nombre de mots de longueur n presents dans le
langage. Ainsi, il est commode dans les exercices de considerer un automate
emondeprive de tels etats. On pourrait ainsi reprendre lexercice precedent
en ne considerant dans lautomate de la gure V.7 que les etats 1 et 2.
Une autre methode fort utile dans le cadre des equations lineaires recur-
rentes consiste ` a utiliser la notion de serie generatrice. Ainsi, si (u
n
)
nN
est
une suite, on note symboliquement
F
u
(X) =
k0
u
k
X
k
96 Chapitre V. Quelques complements sur les langages reguliers
la serie generatrice de cette suite. Il sagit dune mani`ere commode de coder
les elements de (u
n
)
nN
. On peut denir la somme et le produit de deux
series formelles pour munir lensemble des series dune structure danneau.
Proposition V.3.10. Si (u
n
)
nN
satisfait lequation lineaire recurrente ho-
mog`ene de degre k
n 0, u
n+k
=
k
i=1
a
i
u
n+ki
avec comme conditions initiales u
0
= b
0
, . . . , u
k1
= b
k1
, alors la serie
generatrice F
u
est la fraction rationnelle
F
u
(X) =
k1
i=0
b
i
X
i
i+j<k
a
i
b
j
X
i+j
1
k
i=1
a
i
X
i
Demonstration. Il vient
F
u
(X) =
n0
u
n
X
n
=
n0
u
n+k
X
n+k
+
k1
i=0
u
i
X
i
=
n0
_
k
i=1
a
i
u
n+ki
_
X
n+k
+
k1
i=0
b
i
X
i
=
k
i=1
a
i
X
i
n0
u
n+ki
X
n+ki
+
k1
i=0
b
i
X
i
=
k
i=1
a
i
X
i
_
_
F
u
(X)
ki1
j=0
u
j
X
j
_
_
+
k1
i=0
b
i
X
i
On a utilise ci-dessus le fait quil sagit de sommations formelles et quil ny
a donc aucune objection ` a permuter les dierents symboles sommatoires.
Par consequent, on obtient
_
1
k
i=1
a
i
X
i
_
F
u
(X) =
k1
i=0
b
i
X
i
i=1
ki1
j=0
a
i
u
j
X
i+j
do` u la conclusion car
k
i=1
ki1
j=0
a
i
u
j
X
i+j
=
i+j<k
a
i
b
j
X
i+j
.
L
(n) = 3
L
(n 1)
L
(n 2) 2
L
(n 3), n 3.
Considerons la serie generatrice
F(X) =
n0
L
(n) X
n
.
On a
F(X) =
n3
L
(n) X
n
+
L
(2) X
2
+
L
(1) X
1
+
L
(0) X
0
=
n3
[3
L
(n 1)
L
(n 2) 2
L
(n 3)] X
n
+ 3X
2
+ 2X + 1
= 3X [F(X)
L
(0)
L
(1)X] X
2
[F(X)
L
(0)] 2X
3
F(X)
+3X
2
+ 2X + 1
= (3X X
2
2X
3
)F(X) 2X
2
X + 1
et donc
F(X) =
2X
2
+X 1
2X
3
+X
2
3X + 1
=
(2X 1)(X + 1)
(2X 1)(X +
1+
5
2
)(X +
1
5
2
)
.
Si on developpe F(X) en fraction rationnelles, on obtient
F(X) =
X +
1+
5
2
+
X +
1
5
2
et
_
+ = 1
(1
5) +(1 +
5) = 2.
De l` a, on tire
=
5
5
10
, =
5 +
5
10
.
Pour le developpement en serie de puissances, il est utile de rappeler les
relations suivantes
1
1 X
=
k0
k
X
k
.
et
1
(1 X)
2
=
1
D
x
1
1 X
=
k1
k
k1
X
k1
o` u D
x
est une derivation formelle
4
. Dune mani`ere generale,
1
(1 X)
p
est pro-
portionnel ` a D
p1
x
1
1 X
et il sut donc de deriver formellement
k0
k
X
k
.
4
Les details et les justications sortent du cadre de ce cours.
98 Chapitre V. Quelques complements sur les langages reguliers
Ainsi, sur notre exemple, il ne reste plus qu` a developper F(X) en serie de
puissances en utilisant la premi`ere relation pour obtenir
X +
1+
5
2
=
2
1 +
5
1
1 +
2
1+
5
X
=
2
1 +
k0
(
2
1 +
5
)
k
X
k
,
et
X +
1
5
2
=
2
1
5
1
1 +
2
1
5
X
=
2
1
k0
(
2
1
5
)
k
X
k
.
En identiant les coecients, on trouve la formule close recherchee :
L
(n) =
5
5
10
2
1 +
5
. .
53
5
10
(
2
1 +
5
. .
1
5
2
)
n
5 +
5
10
2
1
5
. .
5+3
5
10
(
2
5 1
. .
1+
5
2
)
n
.
On retrouve bien la solution donnee en (4) ` a des reecritures algebriques pr`es.
Pour conclure cette section, on dispose encore du resultat suivant.
Proposition V.3.12. Soit L un langage regulier accepte par un AFD acces-
sible /. Le polyn ome minimum de la matrice dadjacence de / est divisible
par le polyn ome minimum de la matrice dadjacence de lautomate minimal
/
L
de L.
Demonstration. Soit M (resp. N) la matrice dadjacence de lAFD ac-
cessible / = (Q, q
0
, F, , ) (resp. de /
L
= (Q
L
, q
0,L
, F
L
, ,
L
)). Au vu du
theor`eme IV.3.8, pour tous p, q Q
L
et tout mot w de longueur k tel que
L
(p, w) = q, il existe une application : Q Q
L
et des etats p
et q
de Q
tels que
(p
) = p, (q
) = q et
L
((p
), w) = ((p
, w)) = (q
) = q.
q"
q p
p q
w
w
1
(q)
[M
k
]
p
,q
.
V.4. Monode syntaxique 99
En eet, puisque / est deterministe, on ne doit prendre en compte quun
seul p
1
(p) car sinon, on compterait un meme mot plus dune fois.
Par consequent, si M annule un polyn ome
5
, N lannule aussi. En parti-
culier, M annule son polyn ome minimum donc N annule le polyn ome mini-
mum de M. Pour conclure, il sut de se rappeler que le polyn ome minimum
de N divise tout polyn ome annule par N.
4. Monode syntaxique
Lorsquon etudie les langages formels, certaines de leurs proprietes peu-
vent sexprimer en termes algebriques en introduisant la notion de monode
syntaxique. Le but de cette section est de fournir quelques rudiments con-
cernant cet outil puissant
6
.
Denition V.4.1. Soit L
. On a
u
L
v (x, y
et meme
dune congruence (` a droite et ` a gauche), i.e., pour tout ,
u
L
v (u
L
v et u
L
v).
On parle souvent de la congruence syntaxique
L
et on dit que u et v sont
syntaxiquement equivalents.
Remarque V.4.2. Nous avons montre que
L
est une congruence ` a gauche
et ` a droite. Mais en toute generalite, une congruence doit respecter la pro-
priete suivante: si x
L
x
et si y
L
y
, alors xy
L
x
, cest-` a-dire
quelle doit bien se comporter par rapport au produit envisage, ` a savoir ici,
la concatenation. Et ceci est bien le cas car pour tous ,
, il vient
xy L x
y L x
L.
Dans cette section, on notera simplement [w] la classe dequivalence pour
L
etant convenu que la relation
L
est sous-entendue. Bien evidemment,
[w] est un ensemble de mots, donc un langage.
5
Soit P(z) =
P
n
i=0
ai z
i
tel que P(M) = 0. En particulier, pour tous p
, q
,
P
n
i=0
ai (M
i
)
p
,q
= 0 et donc
P
q
1
(q)
P
n
i=0
ai (M
i
)
p
,q
= 0. En permutant les
sommes, on obtient
P
n
i=0
ai
P
q
1
(q)
(M
i
)
p
,q
= 0 puis
P
n
i=0
ai(N
i
)p,q = 0 et donc
P(N) = 0.
6
En eet, on peut par exemple montrer quun langage peut sexprimer ` a partir
densembles nis en utilisant un nombre ni doperations dunion, de concatenation,
dintersection et de complementation (on parle alors ` a juste titre de langage sans etoile,
ou star-free) si et seulement si son monode syntaxique ne contient que des sous-groupes
triviaux. Ce resultat de nature algebrique est d u ` a M.P. Sch utzenberger.
100 Chapitre V. Quelques complements sur les langages reguliers
Exemple V.4.3. Soit L, le langage forme des mots sur a, b ne contenant
pas deux bb consecutifs. On remarque tout dabord que
xay L (x L et y L).
De l` a, on en tire que la classe de a pour la congruence syntaxique
L
est de
la forme
[a] = awa [ w L a.
En particulier, , [a].
Nous allons voir quon peut munir lensemble quotient
/
L
, i.e.,
lensemble des classes dequivalence pour
L
, dune structure de monode.
Denition V.4.4. Soit loperation
:
/
L
/
L
/
L
: ([x], [y]) [x] [y]
denie par
[x] [y] = [z] si [x] [y] [z]
o` u represente loperation de concatenation de langages
7
. Lapplication
est bien denie car au vu de la remarque V.4.2, la denition ne depend pas
du representant choisi.
Remarque V.4.5. Il est evident que
[x] [y] = [xy].
Remarque V.4.6. On remarque queectivement, la concatenation de
deux classes [x] [y] est forme de mots equivalents mais quen general, il
sagit dun sous-ensemble strict de la classe dequivalence [xy].
En considerant ` a nouveau le langage L forme des mots sur a, b ne
contenant pas deux bb consecutifs, on a
[a] [a] = [aa] = [a].
Cependant, le mot aba (ou meme a) appartient bien ` a [a] mais ne peut pas
se factoriser sous la forme
aba = xy avec x, y [a].
Ceci montre bien que [a] [a] [a].
Proposition V.4.7. Muni de loperation , lensemble quotient
/
L
poss`ede une structure de monode.
Demonstration. Le neutre est [], i.e., pour tout x
, on a
[x] [] = [x].
De plus, loperation est associative, i.e., pour tous x, y, z
,
([x] [y]) [z] = [x] ([y] [z]).
7
Operation tout ` a fait naturelle, puisquune classe dequivalence pour L est, comme
nous lavons dej` a remarque, un ensemble de mots. Ainsi, on denit une nouvelle operation
, ` a partir dune ancienne, la concatenation.
V.4. Monode syntaxique 101
Cela resulte de la remarque V.4.5.
/
L
, ) est le monode syntaxique de L.
On note simplement le morphisme canonique
:
/
L
: w [w].
Le resultat suivant fournit un moyen explicite pour rechercher le monode
syntaxique dun langage.
Theor`eme V.4.9. Soient L
un langage et w, w
).
Demonstration. Supposons quil existe dans lautomate minimal de L,
un etat tel que
L
(q, w) ,=
L
(q, w
).
Puisque lautomate minimal est reduit (cf. proposition IV.3.10), il existe
un mot z
tel que
L
(
L
(q, w), z) soit nal et
L
(
L
(q, w
), z) ne le soit
pas (ou reciproquement, mais par souci de simplication, nous supposerons
etre dans un tel cas de gure). De plus, lautomate minimal est accessible.
Cela signie quil existe un mot x
tel que
L
(q
0,L
, x) = q. Sche-
matiquement, nous avons la situation suivante reprise en gure V.10. Par
x
q
w
w
z
z
q
0
Figure V.10. Situation dans lautomate minimal.
consequent, xwz L et xw
ne sont pas
syntaxiquement equivalents.
Passons ` a la reciproque. Si pour tout etat q de /
L
, on a
L
(q, w) =
L
(q, w
L
(q
0,L
, xw) = (q
0,L
, xw
)
et d`es lors, puisque lautomate minimal est deterministe, pour tout y
,
on a
L
(q
0,L
, xwy) =
L
(q
0,L
, xw
y).
Schematiquement, on a la situation representee ` a la gure V.11 Ainsi, pour
tous x, y
,
xwy L xw
y L.
102 Chapitre V. Quelques complements sur les langages reguliers
q
0
w
w
y
x
Figure V.11. Situation dans lautomate minimal.
Soit /
L
= (Q
L
, q
0,L
, F
L
, ,
L
) lautomate minimal dun langage L. A
tout mot w , il correspond une unique fonction f
w
: Q
L
Q
L
denie
par
f
w
: Q
L
Q
L
: q
L
(q, w).
Pour un langage L donne, on note
H
L
= f
w
[ w
.
Muni de loperation de composition de fonctions, H
L
est un monode ayant
id pour neutre. On a f
ww
= f
w
f
w
car pour tout q,
f
ww
(q) = q.ww
= (q.w).w
= f
w
(f
w
(q)).
Corollaire V.4.10. Lapplication
R :
/
L
H
L
: [w] f
w
est un isomorphisme de monodes.
Demonstration. Cela resulte directement du theor`eme precedent. En
eet, deux mots w et w
), alors w ,
L
w
/
L
est ni, alors lautomate minimal de L est
ni et le langage L est regulier.
(q) f
a
(q) f
b
(q) f
aa
(q) f
ab
(q) f
ba
(q)
1 1 2 1 3 1 2
2 2 3 1 3 3 2
3 3 3 3 3 3 3
Cet ensemble aurait pu contenir au plus 3
3
= 27 fonctions. Pour verier
quil ny a pas dautres applications dans H
L
, on peut construire de proche
en proche un graphe ni de la mani`ere suivante. Si Q
L
= 1, . . . , n, alors
on initialise la construction avec un unique sommet correspondant au n-uple
detats (1, . . . , n). Ensuite, on applique les fonctions f
, , ` a chaque
etat nouvellement cree. Si (q
1
, . . . , q
n
) est un etat du graphe, alors on trace
un arc de label joignant ce sommet au sommet (f
(q
1
), . . . , f
(q
n
)). La
procedure sarrete lorsque plus aucun nouvel etat nest cree. Lapplication
de cette procedure donne le graphe de la gure V.13.
(1,2,3)
(1,1,3)
(2,3,3) (1,3,3)
(2,2,3)
(3,3,3)
a,b
b
a
b
b
a
a
a
b
a
b
Figure V.13. Graphe associe ` a H
L
.
Deux mots w et w
).
En resume, on sinterdit dutiliser letoile de Kleene.
Remarque V.5.2. Il serait facile de denir les expressions reguli`eres sans
etoile permettant de generer exactement les langages reguliers sans etoile. Il
sut pour cela dadapter les r`egles de construction donnees ` a la denition
I.3.1.
Exemple V.5.3. Soit = a, b. Par exemple,
.
Le langage L des mots sur ne contenant pas le facteur aa est aussi sans
etoile. En eet,
L =
aa
)
et nous avons vu que
(b
a +
aa
bb
).
Comme le montre ce dernier exemple, il peut etre assez dicile de deter-
miner si un langage donner peut ou non etre mis sous une formesans etoile.
En particulier, comment pouvons-nous demontrer quun langage regulier
donne nest pas sans etoile ?
Nous allons voir que la theorie du monode syntaxique permet de donner
un algorithme ecace pour repondre ` a cette question.
Les resultats suivants sont dapplication dans tout semi-groupe ni. Rap-
pelons quun semi-groupe est un ensemble muni dune operation (binaire,
interne et partout denie) associative
8
. Dans un semi-groupe S, un element
e est qualie de neutre si
s S, s e = s = e s.
8
Un monode est un semi-groupe possedant un neutre.
106 Chapitre V. Quelques complements sur les langages reguliers
De meme, un element e est qualie de zero si
s S, s e = e = e s.
Proposition V.5.4. Si un semi-groupe poss`ede un neutre (resp. un zero),
alors celui-ci est unique.
Demonstration. Cest trivial.
).
6.2. Probl`emes de denombrement.
Exercice V.6.2. Soit L
L
(n) = n
2
.
Meme question avec cette fois,
L
(n) = n
3
.
Exercice V.6.3. On consid`ere le langage L forme des mots sur a, b ayant
un nombre impair de b.
Quel est lautomate minimal de L ?
Donner la matrice dadjacence de cet automate.
En deduire une relation de recurrence lineaire pour
L
(n).
110 Chapitre V. Quelques complements sur les langages reguliers
Trouver une formule close pour
L
(n).
Exercice V.6.4. On consid`ere le langage L forme des mots sur a, b, c
ne commen cant pas par c et ne contenant pas le facteur ac.
Quel est lautomate minimal de L ?
Soit la serie generatrice
F(X) =
n0
L
(n) X
n
.
Montrer que
F(X) =
1 X
X
2
3X + 1
.
En deduire une formule close pour
L
(n).
Exercice V.6.5. On consid`ere le langage L = a
.
Quel est lautomate minimal de L ?
Donner la matrice dadjacence de cet automate.
En deduire une relation de recurrence lineaire pour
L
(n).
Montrer que la serie generatrice de
L
(n) est de la forme
F(X) =
1
(1 X)
2
En developpant en serie de puissances, en conclure que
L
(n) =
n + 1.
Exercice V.6.6. On consid`ere lalphabet = a, b, c et le langage regulier
sur forme des mots ne contenant pas le facteur aa. Ce langage est ac-
cepte par lautomate ni deterministe / = (1, 2, 3, 1, 1, 2, , ) o` u la
fonction de transition : 1, 2, 3 1, 2, 3 est donnee par
a b c
1 2 1 1
2 3 1 1
3 3 3 3.
Donner une relation de recurrence lineaire pour la suite
L
(n) =
#(L
n
) comptant le nombre de mots de longueur n dans L.
Par une methode au choix, en deduire une formule close pour
L
(n).
6.3. Monode syntaxique et langages sans etoile.
Exercice V.6.7. Soit L un langage. Demontrer que L est une union de
classes dequivalence pour la congruence syntaxique
L
.
Exercice V.6.8. Soit L = a
tels que
q
1
.w = q
1
, . . . , q
r
.w = q
r
o` u est une permutation de 1, . . . , r distincte de lidentite.
V.6. Exercices 113
Exercice V.6.16. Demontrer quun langage regulier est sans etoile si et
seulement si son automate minimal est sans permutation.
CHAPITRE VI
Introduction aux langages algebriques
Les chapitres precedents nous ont donnes un aper cu assez complet des
langages reguliers et de leurs principales proprietes. En particulier, nous
avons constate, et ce ` a plusieurs reprises, que des langages comme a
n
b
n
[
n N, pourtant relativement simples dun point de vue syntaxique,
netaient pas reguliers. Dans les pages qui suivent, nous allons presenter
une famille de langages qui sont generes par des methodes plus riches que
les expressions reguli`eres. Plus precisement, nous allons introduire la notion
de grammaire hors contexte. Un langage genere par une telle grammaire
sera dit algebrique (ou hors contexte). Historiquement, ces langages ont ete
introduits
1
par N. Chomsky dans le but initial de formaliser les proprietes
grammaticales de langues naturelles comme langlais ou le fran cais. Il sest
avere par la suite que ces notions etaient particuli`erement bien adaptees ` a
la syntaxe des langages de programmation.
1. Premi`eres denitions
Commen cons par un exemple introductif presentant le concept de gram-
maire.
Exemple VI.1.1. Pour construire une phrase grammaticalement correcte
en fran cais, on peut proceder comme suit
PHRASE SUJET VERBE COMPLEMENT
SUJET LUDOVIC [ MICHEL [ NICOLAS [ THIERRY
VERBE VOIT [ MANGE [ PORTE
COMPLEMENT ARTICLE NOM ADJECTIF
ARTICLE UN [ LE
NOM LIVRE [ PLAT [ WAGON
ADJECTIF BLEU [ ROUGE [ VERT
Ainsi, sans vouloir formaliser plus que necessaire, avec les r`egles don-
nees ci-dessus, on peut construire au moyen de substitutions successives des
phrases comme
NICOLAS PORTE UN LIVRE VERT
ou
MICHEL MANGE LE WAGON BLEU.
1
N. Chomsky, On certain formal properties of grammars, Inform. and Control, 137
167, 1959.
115
116 Chapitre VI. Introduction aux langages algebriques
On peut formaliser cet exemple de la mani`ere suivante.
Denition VI.1.2. Soient V et deux alphabets nis (supposes disjoints).
Une grammaire hors contexte, ou grammaire algebrique, est la donnee dun
4-uple
G = (V, , P, S)
o` u P V (V )
, alors on note
A w
1
[ w
2
[ [ w
n
.
Si w peut secrire xAy avec A V et x, y (V )
, alors on note
w
G
z
lorsque z = xuy avec (A, u) P. On dit alors que z est obtenu gr ace ` a une
derivation de longueur 1. En dautres termes, on a remplace dans w une
occurence dun non terminal A par le second membre u dune production
A u de G ayant A comme premier membre. Si G est sous-entendu, on
sautorise ` a ecrire simplement au lieu de
G
. On note
la fermeture
reexive et transitive de . Ainsi, w
, n 0, tels que
w w
1
w
2
w
n
z.
Dans ce dernier cas, on dit que z est obtenu ` a partir de w par une derivation
de longueur n + 1. Enn, le langage genere par G est lensemble des mots
de qui sobtiennent par derivation ` a partir du symbole initial S, i.e.,
L(G) = w
[ S
w.
Un langage L
, A
i
V et y
i
(V )
,
pour tout i 1, . . . , n. Alors, cette derivation est une derivation ` a gauche.
Cela signie qu` a chaque etape, on a substitue la variable la plus ` a gauche.
On denit de mani`ere semblable une derivation ` a droite. Comme le montre
une fois encore lexemple precedent, pour une grammaire G xee, un mot
appartenant ` a L(G) peut avoir plus dune derivation ` a gauche
2
. Il est aussi
clair que si un mot appartient ` a L(G), il poss`ede au moins une derivation ` a
gauche. Si tout mot de L(G) poss`ede exactement une derivation ` a gauche,
alors la grammaire G est qualiee de non ambigue. Un langage algebrique
est non ambigu sil existe une grammaire non ambigue qui le gen`ere. Nous
verrons ` a la section 3 en quoi le caract`ere non ambigu est important dun
point de vue pratique
3
.
2
On peut montrer que le nombre de derivations ` a gauche dun mot de L(G) est egal au
nombre de derivations ` a droite permettant dobtenir ce meme mot. Ainsi, il est equivalent
de denir une notion, comme le caract`ere non ambigu, sur le nombre de derivations ` a
gauche ou ` a droite.
3
Pour plus dinformation ` a propos de lutilisation des grammaires dans lecriture
dun compilateur, voir par exemple la page http://dinosaur.compilertools.net/ o` u
lon presente les outils Lex, Yacc, Flex et Bison
118 Chapitre VI. Introduction aux langages algebriques
Considerons encore deux autres exemples de grammaires.
Exemple VI.1.5. La grammaire ci-dessous gen`ere exactement le langage
a
n
b
n
[ n N. Considerons G = (V, , P, S) o` u V = S, = a, b, et
les productions de G donnees par
S aSb [ .
Ce langage est trivialement non ambigu. En eet, pour chaque mot w du
langage L(G) il existe une seule suite de r`egles de G permettant dobtenir
w ` a partir de S.
Exemple VI.1.6 (Langage de Dyck). On consid`ere lalphabet
= a
1
, a
1
, . . . , a
n
, a
n
,
la grammaire G = (V, , P, S) o` u V = S, T et les productions de P don-
nees par
S ST [
T a
1
S a
1
[ [ a
n
S a
n
.
Le langage genere par la grammaire G sappelle le n-i`eme langage de Dyck
et se note D
n
. Il est facile de voir quil sagit exactement du langage forme
des mots bien parenth`eses lorsquon dispose de n niveaux de parenth`esage
(la j-i`eme parenth`ese ouvrante etant symbolisee par a
j
et la j-i`eme paren-
th`ese fermante correspondante par a
j
). En guise dillustration, considerons
lalphabet = ( ), [ ] forme de parenth`eses et de crochets et les productions
S ST [
T ( S ) [ [ S ].
On obtient par exemple les mots suivants
S ST S(S) (S) ( ),
S ST S(S) ST(S) ST( )
ST( ) S[S]( ) S[S]( ) S[ ]( ) [ ]( ),
S ST S(S) S(ST) S(S(S))
S(S(ST)) S(S(STT))
((( )( ))).
Noter que, dans un langage de Dyck, il ny a pas de preseance sur lordre des
dierentes parenth`eses. Ainsi, les mots [( )] et ([ ]) sont tous deux valides.
Dans le cas de lalphabet = a, a, on peut encore montrer quun mot
w appartient au premier langage de Dyck D
1
si et seulement si les deux
conditions suivantes sont satisfaites
pour tout i 1, . . . , n, [w[
a
= [w[
a
pour tout prexe u de w, [u[
a
[u[
a
.
VI.2. Arbres danalyse 119
2. Arbres danalyse
Dans cette section, nous allons montrer qu` a une derivation correspond
un arbre, appele arbre danalyse, et reciproquement, ` a tout arbre danalyse
correspond au moins une derivation. Nous supposerons
4
quaucun second
membre des productions des grammaires rencontrees nest egal ` a .
Pour rappel, en theorie des graphes, un arbre est un graphe connexe
sans cycle. Par commodite, nous allons preferer une denition recursive des
arbres. Soit E, un ensemble ni dont les elements sont appeles noeuds. Les
arbres de hauteur 0 sont les elements e de E. On les note (e, ) et e est
la racine de larbre. Si e E et /
1
, . . . , /
n
sont des arbres respectivement
de hauteur h
i
et de racine e
i
, i = 1, . . . , n, alors, en connectant e aux dif-
ferents e
i
, on denit (e, (/
1
, . . . , /
n
)) comme etant un arbre de racine e, de
hauteur 1+sup
i
h
i
et de sous-arbres /
1
, . . . , /
n
. Dans cette denition, le n-
uple (/
1
, . . . , /
n
) est ordonne. Ainsi, si est une permutation distincte de
lidentite, (e, (/
1
, . . . , /
n
)) ,= (e, (/
(1)
, . . . , /
(n)
)). On dit que les noeuds
e
1
, . . . , e
n
sont les ls de e (ou que e est le p`ere des e
i
). Si f E appartient
` a un des sous-arbres /
i
, alors f est un descendant de e (ou e est un ancetre
de f). En particulier, la racine dun arbre de hauteur 0 na pas de ls (ce
qui explique la notation (e, )). Un arbre de racine e ayant trois sous-arbres
/
1
, /
2
, /
3
est represente schematiquement ` a la gure VI.1. La hauteur de
e
e
1
e e
3 2
A
A
A
1
2
3
Figure VI.1. Un arbre.
larbre / (resp. /
1
, /
2
, /
3
) est 5 (resp. 4, 2, 3).
Denition VI.2.1. Soit G = (V, , P, S) une grammaire hors contexte.
Pour tout A V , (A, ) est un arbre danalyse de G. Si A A
1
A
n
est une production de G, A
i
V , et si /
1
, . . . , /
n
sont des arbres
danalyse de G de racine respective A
1
, . . . , A
n
, alors (A, (/
1
, . . . , /
n
)) est
encore un arbre danalyse de G. Cette denition est recursive et permet de
construire de proche en proche
5
les arbres danalyse de G.
4
Nous verrons plus tard quil est toujours possible de se ramener ` a une telle situation.
5
par hauteur croissante.
120 Chapitre VI. Introduction aux langages algebriques
Exemple VI.2.2. Poursuivons lexemple VI.1.3. Voici quelques arbres
danalyse de G representes ` a la gure VI.2.
S
A A
A
b
a
a
A
A b
A A
S
A A A
A
a
A
A
S
a
Figure VI.2. Des arbres danalyse.
Denition VI.2.3. Soit / un arbre danalyse de G. Le fruit de /, note
T(/), est un mot deni recursivement. Si larbre est de hauteur nulle, i.e.,
si / = (B, ), B V , alors T(/) = B. Sinon, il existe des arbres
danalyse /
1
, . . . , /
n
tels que / = (B, (/
1
, . . . , /
n
)). Dans ce cas, on pose
T(/) = T(/
1
) T(/
n
).
Loperation envisagee ici est bien evidemment la concatenation des fruits
respectifs des dierents sous-arbres.
Exemple VI.2.4. Si on reprend les arbres danalyse de G representes ` a la
gure VI.2, les fruits de ces arbres sont respectivement
A, S, a, AA, AAA, a, Ab, aab.
Il est clair qu` a une derivation correspond un arbre danalyse. On cons-
truit cet arbre de proche en proche ` a partir de larbre danalyse (S, ). A
chaque fois quune variable est substituee, on gree le sous-arbre correspon-
dant ` a la r`egle qui a ete appliquee. Considerons un exemple.
Exemple VI.2.5. Poursuivons lexemple VI.1.3. Nous avions obtenu la
derivation suivante du mot ababaa.
S AA aA aAAA
abAAA abaAA ababAA ababaA ababaa.
Pour chacune des productions considerees, on obtient de proche en proche
larbre danalyse represente ` a la gure VI.3. Lorsquune production est
appliquee ` a une variable donnee, on ajoute le sous-arbre correspondant ` a
larbre danalyse dej` a obtenu. A chaque etape, le fruit de larbre est modie
en consequence pour obtenir nalement un arbre de racine S et de fruit
ababaa.
VI.2. Arbres danalyse 121
A
A A A
A
b
S
A A b
a
a
A
A A A
A
b
S
A A b
a a
a
A
A A A
A
b
S
a A A b
a a
a
A
A b
A
A A
A
S
a
A
A A A
A
S
A b
a
a
A A
S
a
A
A A
A
S
a
A
A A
S
Figure VI.3. Arbres danalyse provenant de derivations.
Reciproquement, ` a un arbre danalyse de G de sommet S et de fruit w
appartenant ` a
, il correspond
6
au moins une suite de r`egles produisant
w ` a partir de S. Dans cet arbre, lorsque deux symboles non terminaux se
trouvent au meme niveau
7
, il nest pas possible de savoir quelle r`egle de
derivation est appliquee avant quelle autre. Par consequent, il ny a pas
unicite dans lordre dapplication des r`egles de la grammaire. Par exemple,
le dernier arbre de derivation obtenu ` a la gure VI.3 et ayant ababaa pour
6
Cette correspondance existe pour tout arbre danalyse, pas seulement ceux de racine
S et de fruit terminal. En eet, ` a tout arbre de racine A V et fruit w (V )
, il
correspond une suite de r`egles produisant w ` a partir de A.
7
Dans un arbre, le niveau dun noeud est la longueur du chemin menant de la racine
` a ce noeud.
122 Chapitre VI. Introduction aux langages algebriques
fruit correspond egalement ` a la suite de r`egles
S AA AAAA AAbAA AAbAa
AAbaa aAbaa abAbaa ababaa.
Neanmoins, ` a un arbre danalyse donne, il correspond une seule derivation ` a
gauche. Cela revient ` a parcourir larbre (de mani`ere recursive) comme suit
Si larbre est reduit ` a la racine n du parcours.
Sinon, / = (B, (/
1
, . . . , /
n
)) et parcourir, dans lordre, les sous-
arbres /
1
, . . . , /
n
.
Le parcours P dans larbre fournit la suite de r`egles ` a appliquer pour obtenir
la derivation ` a gauche.
Exemple VI.2.6. Considerons larbre represente ` a la gure VI.4. A cet
A b
a
a
A b
a
A A A
A
b A
S
A
a
Figure VI.4. Un arbre danalyse.
arbre correspond lunique derivation ` a gauche
S AA AAAA bAAAA baAAA baaAA baabAA
baabbAA babbaA babbaa.
Remarque VI.2.7. Une adaptation immediate permet dobtenir la deriva-
tion ` a droite associee ` a un arbre. Si / = (B, (/
1
, . . . , /
n
)) nest pas reduit
` a une racine, parcourir, dans lordre, les sous-arbres /
n
, . . . , /
1
.
3. Une illustration de lambiguite
Considerons la grammaire G = (N, , P, E) o` u N = E, N, C (on
utilise ici les lettres E, N et C comme dans Expression, Nombre et Chire),
= +, , , /, (, ), 0, 1, . . . , 9
et o` u les r`egles sont
VI.3. Une illustration de lambiguite 123
E (E) [ E +E [ E E [ E E [ E/E [ N
N C [ NC
C 0 [ 1 [ [ 9.
Cette grammaire gen`ere des expressions arithmetiques elementaires (on sau-
torise de plus, pour ne pas alourdir lexpose, ` a ecrire des nombres com-
men cant par 0).
Considerons le mot 1 2 +3 appartenant au langage genere par cette
grammaire. Ce mot est obtenu par la derivation ` a gauche
E E +E E E +E N E +E C E +E 1 E +E
1 N +E 1 C +E 1 2 +E 1 2 +N 1 2 +C
1 2 + 3.
A cette derivation correspond larbre danalyse represente ` a la gure VI.5.
Le mot 1 2 + 3 est aussi obtenu par la derivation ` a gauche
E
1 2
3
E E
E E
+
N
N
N
C C
C
Figure VI.5. Un arbre danalyse pour 1 2 + 3.
E E E N E C E 1 E 1 E +E
1 N +E 1 C +E 1 2 +E 1 2 +N 1 2 +C
1 2 + 3.
A cette derivation correspond larbre danalyse represente ` a la gure VI.6.
Lorsquon dispose dun arbre danalyse
8
(que ce soit celui de la gure VI.5 ou
celui de la gure VI.6), le parcours recursif P de cet arbre o` u lon consid`ere ` a
chaque fois, en premier lieu, le sous-arbre le plus ` a gauche, permet devaluer
8
En general, lors de la phase de compilation dun programme, ou dans le cas plus
simple qui nous interesse ici, linterpretation dune formule, la premi`ere etape conee ` a
lanalyseur est de determiner un arbre danalyse. Une fois larbre danalyse connu, on
peut specier le sens ` a donner aux dierents noeuds. La semantique est particuli`erement
simple dans le cadre decrit ici puisquil ne sagit que dexpressions arithmetiques. Pour
un programme ` a compiler, on pourrait imaginer devoir realiser lallocation de memoire,
ladressage de variables, etc...
124 Chapitre VI. Introduction aux langages algebriques
E
E
N
2 3
1
N
E E
+
N
E
C
C C
Figure VI.6. Un arbre danalyse pour 1 2 + 3.
les expressions envisagees. Si on consid`ere larbre de la gure VI.5, le sous-
arbre de gauche a pour valeur 1 2, celui de droite 3 et donc, la valeur
assignee ` a larbre est
(1 2) + 3 = 2.
Par contre, si on consid`ere ` a present larbre de la gure VI.6, le sous-arbre
de gauche a pour valeur 1 et celui de droite 2+3. D`es lors, la valeur assignee
est cette fois
1 (2 + 3) = 4.
Remarquons quil sagit une fois encore dune derivation ` a gauche,
E E E
1 E 1 E +E
1 2 + 3.
Ainsi, suivant larbre choisi, les groupements de termes sont realises en par-
tant de la gauche ou de la droite et la valeur assignee nest pas necessairement
la valeur attendue.
Si les operateurs nont pas la meme preseance, la grammaire proposee
peut regrouper un operateur de faible preseance avant un operateur de
preseance plus elevee. En eet, considerons le mot 2+35. A ce mot, il cor-
respond les arbres danalyse representes ` a la gure VI.7 . Ainsi, levaluation
de larbre de gauche fournit la valeur (2 + 3) 5 alors que pour larbre de
droite, on trouve 2 + (3 5).
Cet exemple montre bien le probl`eme que pose en pratique lutilisation
dune grammaire ambigue. En eet, le compilateur ou linterpreteur
9
na
pas les moyens de determiner quel arbre danalyse permet dassigner une
valeur correcte ` a lexpression envisagee. Ainsi, lors de la specication dun
compilateur, il faut veiller ` a employer une grammaire non ambigue.
Revenons sur le probl`eme des expressions arithmetiques. Lecueil prin-
cipal de la grammaire presentee ci-dessus est quelle ne tient pas compte de
9
Le r ole dun compilateur est de transformer un code source en un autre code.
Par exemple, transformer un texte codant un programme ecrit en C en un code machine
intelligible par le processeur ou le syst`eme dexploitation ou encore, transformer un texte
comprenant des instructions LaTeX en un chier .dvi achable ` a lecran.
VI.3. Une illustration de lambiguite 125
E
*
5
E
N N
E
+
3
2
N
E
E
E
N
N
E E
N
E
*
+
2
3 5
C C
C C
C C
E
Figure VI.7. Deux arbres danalyse pour 2 + 3 5.
lordre de preseance des operations ` a eectuer. Pour y remedier et obtenir
une grammaire hors contexte non ambigue, nous proposons (sans preuve) la
grammaire suivante. Les symboles non terminaux sont E, T, F, N, C o` u T et
F sont employes pour rappeler les mots Terme et Facteur. Les r`egles sont
E E +T [ E T [ T
T T F [ T/F [ F
F (E) [ N
N C [ NC
C 0 [ 1 [ [ 9.
La distinction faite ici entre expressions, termes et facteurs force le groupe-
ment correct des operateurs ` a dierents niveaux de preseance. La gure VI.8
reprend les arbres danalyse des expressions 1 2 + 3 et 2 + 3 5.
F
N
C
3
F
N
C
2
T
F
N
C
1
T
F
N
C
E
E
E
N
E
*
+
5
C
+
E
T
T
T F
F
N
C
3
T
2
Figure VI.8. Arbres danalyse de 1 2 + 3 et 2 + 3 5
pour une grammaire non ambigue.
126 Chapitre VI. Introduction aux langages algebriques
Signalons pour conclure, quon peut aisement enrichir cette derni`ere
grammaire dautres operateurs comme lexponentiation ou encore les fonc-
tions trigonometriques, etc. . .
4. Grammaires et langages reguliers
Le but de cette section est de montrer que lensemble des langages
reguliers est un sous-ensemble (strict
10
) de lensemble des langages algebriques.
Pour ce faire, nous allons utiliser la proposition I.3.6 en montrant que la
famille des langages algebriques contient le langage vide, les langages ,
, et est stable pour lunion, la concatenation et letoile de Kleene.
Remarque VI.4.1. La grammaire G = (S, , P, S) o` u lunique r`egle est
S , , gen`ere le langage . De meme, si P = , le langage genere
est .
Proposition VI.4.2. Lensemble des langages algebriques est stable pour
lunion.
Demonstration. Soit G
1
= (V
1
, , P
1
, S
1
) (resp. G
2
= (V
2
, , P
2
, S
2
))
une grammaire generant L
1
(resp. L
2
). On peut supposer que V
1
V
2
=
et que S , V
1
V
2
. La grammaire G = (SV
1
V
2
, , P, S) o` u P contient
P
1
P
2
et la r`egle
S S
1
[ S
2
,
gen`ere exactement L
1
L
2
. Les justications sont laissees au lecteur ` a titre
dexercice.
1
.
10
Nous savons dej` a que {a
n
b
n
| n N} est algebrique et non regulier.
VI.4. Grammaires et langages reguliers 127
Corollaire VI.4.5. Lensemble des langages reguliers sur un alphabet ni
est un sous-ensemble de lensemble des langages algebriques.
Demonstration. Cela resulte directement de la remarque VI.4.1, des trois
propositions precedentes et de la proposition I.3.6.
.
Une grammaire hors contexte est reguli`ere (` a droite) si toute production
de G poss`ede une des trois formes suivantes :
A a
A aB
A .
De meme, une grammaire est reguli`ere ` a droite si les seconds membres de
ses productions appartiennent tous ` a
V .
Exemple VI.4.7. Soit la grammaire G = (V, , P, S) o` u V = S, A, B,
= a, b et o` u les productions sont
S aB [
B bS [ bA
A aA [ .
Il est facile de voir que le langage genere par G est exactement
(ab)
ab(a)
b et B
Ba.
128 Chapitre VI. Introduction aux langages algebriques
Remarque VI.4.9. Signalons que les grammaires reguli`eres sont des cas
particuliers de grammaire dont les seconds membres des productions ap-
partiennent tous ` a
.
Remarque VI.5.2. Les grammaires hors contexte sont donc des cas par-
ticuliers de grammaire non restrictive. En eet, dans une grammaire hors
contexte, le premier membre des r`egles est reduit ` a des mots dune lettre sur
lalphabet V .
Exemple VI.5.3. La grammaire non restrictive G = (V, , P, S) telle que
V = S, A, C, = a, b, c et dont les r`egles sont donnees par
S aAbc [
A aAbC [
Cb bC
Cc cc
gen`ere le langage a
n
b
n
c
n
[ n N. En eet,
S aAbc aaAbCbc
a(a)
i
A(bC)
i
bc
a(a)
i
(bC)
i
bc = (a)
i+1
b(Cb)
i
c
(a)
i+1
(b)
i+1
C
i
c
(a)
i+1
(b)
i+1
(c)
i+1
.
Remarque VI.5.4. On peut montrer quun langage L est genere par une
grammaire non restrictive si et seulement si L est recursivement enumerable
12
(i.e., accepte par une machine de Turing).
Dans la hierarchie de Chomsky, entre les grammaires hors contexte et
les grammaires non restrictives, il existe encore un type de grammaire.
Denition VI.5.5. Une grammaire non restrictive G = (V, , P, S) est de
type 1, aussi appelee grammaire dependant du contexte [Context-sensitive
grammar], si toutes les productions u v de G satisfont
12
cf. le cours de calculabilite.
VI.5. A propos de la hierarchie de Chomsky 129
u, v (V )
[u[ [v[.
Si une grammaire satisfait cette derni`ere condition, on parle parfois de gram-
maire non contractante ou monotone car la longueur des mots produits crot
` a chaque application dune nouvelle r`egle. On autorise de plus une unique
r`egle de la forme S .
Remarque VI.5.6. Une denition equivalente de grammaire dependant
du contexte G = (V, , P, S) est de specier les productions de P sous la
forme
N v
o` u , (V )
, N V , v (V )
1
N
1
1
v
1
1
et
2
N
2
2
v
2
2
avec v
1
,= v
2
si (
1
,
1
) ,= (
2
,
2
).
Exemple VI.5.7. La grammaire presentee dans lexemple VI.5.3 nest pas
monotone ` a cause des productions S et A . Il est facile de verier
que la grammaire suivante gen`ere encore le meme langage,
S aAbc [ abc
A aAbC [ abC
Cb bC
Cc cc.
Cette derni`ere est bien une grammaire monotone dependant du contexte.
Remarque VI.5.8. Une fois encore, on peut montrer que tout langage
genere par une grammaire dependant du contexte est recursif
13
(i.e., decide
par une machine de Turing). Plus precisement, les langages generes par une
grammaire dependant du contexte sont exactement les langages decides par
les machines de Turing dont la memoire disponible est bornee de mani`ere
lineaire par la taille des donnees. En dautres termes, on ne sautorise pas un
ruban de longueur arbitraire mais ` a chaque execution, la longueur du ruban
disponible est proportionnelle ` a la taille des donnees fournies ` a la machine
de Turing.
Le tableau suivant recapitule les divers faits enonces dans cette section.
13
cf. le cours de calculabilite.
130 Chapitre VI. Introduction aux langages algebriques
generateur langage accepteur
0 grammaire non restrictive recursivement machine de Turing
enumerable
1 grammaire dependant du contexte dependant du contexte machine de Turing
` a memoire lineaire
2 grammaire hors contexte hors contexte automates ` a pile
3 expression reguli`ere regulier AFD
Les automates ` a pile, accepteurs des langages algebriques, seront presen-
tes dans une prochaine section.
Remarque VI.5.9. Au vu du tableau precedent, on dispose des inclusions
suivantes
Reg Lin Alg DP RE
o` u les dierentes abreviations designent respectivement lensemble des lan-
gages reguliers, lineaires (cf. remarque VI.4.9), algebriques, dependants du
contexte et recursivement enumerables.
Remarque VI.5.10. Le lecteur attentif pourrait emettre une objection
quant ` a la denition de grammaire dependant du contexte o` u lon interdit
la production du symbole , alors que cette restriction nest pas presente
pour les grammaires hors contexte (qui sont cependant un cas particulier de
grammaires de type 1). En fait, comme nous allons le voir dans la section
suivante, on peut aussi se debarasser des r`egles A dans les grammaires
hors contexte. De plus, si une grammaire dependant du contexte doit ef-
fectivement pouvoir generer le mot vide, on se permet dutiliser une unique
r`egle S .
6. Formes normales
Lorsquon sinteresse ` a un langage algebrique L donne, la grammaire
generant L nest pas necessairement unique. Ainsi, on peut desirer avoir
` a sa disposition une grammaire dont les r`egles poss`edent une forme partic-
uli`ere. Lorsquon impose certaines restrictions sur les seconds membres des
productions, on parle de grammaire mise sous forme normale. Nous mon-
trons dans cette section que de telles simplications sont toujours possibles.
Rappelons que deux grammaires sont equivalentes si elles gen`erent le meme
langage.
6.1. Elimination des r`egles A .
Exemple VI.6.1. Dans une derivation produisant un mot terminal, il se
peut quapparaissent des variables ne generant aucun symbole terminal. Ces
variables sont eliminees gr ace ` a des r`egles de la forme A que nous ap-
pelerons -production. Un tel phenom`ene fait grossir inutilement la longueur
des mots intermediaires produits. Par exemple, considerons les r`egles
VI.6. Formes normales 131
S SaB [ aB
B bB [ .
La derivation ` a gauche generant le mot aaa gen`ere trois B qui seront chacun
elimines par lapplication de la r`egle B . Ainsi, on a
S SaB SaBaB aBaBaB aaBaB aaaB aaa.
Denition VI.6.2. On appelle variable ea cable toute variable A telle que
A
.
Si une grammaire ne contient aucune variable ea cable, alors u v entrane
[u[ [v[. On est d`es lors en presence dune grammaire monotone (appliquer
une r`egle ne peut faire diminuer la longueur du mot obtenu).
Nous presentons maintenant un algorithme
14
permettant de detecter les
variables ea cables. Posons
E
0
= A V [ A P.
Si E
0
= , lalgorithme sach`eve et la grammaire ne poss`ede aucune variable
ea cable. Sinon, pour i 0, on denit
E
i+1
= E
i
A V [ w E
i
: A w P.
Puisque V est ni, la suite des E
i
se stabilise. Il est clair que le plus grand
E
i
apparaissant dans cette suite est lensemble des variables ea cables. Une
condition darret pour lalgorithme revient ` a tester legalite de E
i
et E
i+1
.
Proposition VI.6.3. Soit G = (V, , P, S) une grammaire hors contexte.
Il existe une grammaire G
= (V
,
, P
, S
sont equivalentes,
S
,
si appartient ` a L(G) = L(G
. Sinon, G
. On denit V
comme etant
V S
et pour denir P
S. De
cette mani`ere, le nouveau symbole initial S
G
w, alors S
G
S
w.
Au vu de lalgorithme precedent, on sait determiner de mani`ere effective
lensemble E des variables ea cables de G
. Toute r`egle de G
de la forme
A w
1
A
1
w
2
A
2
w
n
A
n
w
n+1
14
ayant une approche bottom-up.
15
Cela signie quil ne sagit pas dun theor`eme existentiel mais bien dun theor`eme
constructif. La preuve fournit une demarche, un algorithme, permettant dobtenir la
grammaire proposee.
132 Chapitre VI. Introduction aux langages algebriques
avec A V , A
1
, . . . , A
n
E, w
1
, . . . , w
n+1
((V ) E)
est remplacee
par les r`egles
A w
1
x
1
w
2
x
2
w
n
x
n
w
n+1
o` u chaque x
i
peut prendre la valeur A
i
ou . Une r`egle est donc remplacee
par au plus 2
n
nouvelles r`egles. Il est clair que cette modication nalt`ere
pas le langage genere puisquon a eventuellement enleve, des seconds mem-
bres des productions, des variables ea cables. (Remarquons quon ne peut
pas simplement supprimer ces variables car une variable ea cable peut etre
utilisee dans la production dun mot terminal.)
La derni`ere etape revient ` a supprimer (de fa con recursive) les r`egles de
la forme A .
Supprimer les -productions, A , modier P
en consequence,
si une variable A apparat uniquement comme premier membre
dune -production, leacer des seconds membres des autres pro-
ductions. Cette etape pouvant creer de nouvelles -productions,
repeter si necessaire le point precedent.
A la n de cette procedure, si S
S
S ACA
A aAaD [ B [ C
B bB [ b
C cS [
D .
Appliquons lalgorithme de recherche des variables ea cables. On trouve
E
0
= C, D, E
1
= A, C, D, E
2
= S, A, C, D et E
3
= S
, S, A, C, D = E.
En suivant la preuve precedente, on remplace les r`egles comme suit
VI.6. Formes normales 133
S
S [
S ACA [ CA [ AA [ AC [ A [ C [
A aAaD [ B [ C [ aAa [ aaD [ aa [
B bB [ b
C cS [ c [
D .
Il ne reste plus qu` a eliminer les -productions. En particulier, puisque D
est le premier membre de lunique r`egle D , on peut supprimer D de
tous les seconds membres. On a
S
S
S ACA [ CA [ AA [ AC [ A [ C
A aAa [ B [ C [ aa
B bB [ b
C cS [ c.
Cette derni`ere grammaire gen`ere le meme langage que la grammaire de de-
part ` a lexception du mot vide (en eet, E). Pour obtenir une grammaire
equivalente, il sut dajouter la r`egle S
.
Ainsi, on peut toujours se ramener ` a une grammaire essentiellement
monotone. Ladjectif essentiellement stipule quon autorise lunique -pro-
duction S permettant de generer le mot vide et que le symbole initial
S napparat dans aucun second membre des r`egles.
6.2. Elimination des r`egles A B.
Remarque VI.6.5. Une r`egle de la forme A B, A, B V , revient
simplement ` a renommer une variable A en B. On dira dune telle r`egle quil
sagit dune 1-production. Dans le cas A A, on parle de 1-production
circulaire.
Denition VI.6.6. Soient A, A
1
, . . . , A
n
, B des variables dune grammaire
G. Une derivation de la forme
A A
1
A
n
B,
o` u chaque production est une 1-production, est une chane.
Soit A une variable etant le premier membre dune 1-production. Lalgo-
rithme suivant
16
permet de determiner toutes les variables apparaissant dans
une chane debutant en A. Posons C
0
= A et C
1
= . Pour i 0,
C
i+1
= C
i
C V [ B C
i
C
i1
: B C P.
La procedure sarrete lorsque C
i
= C
i+1
. On notera ce dernier ensemble
((A). Une fois encore, puisque V est ni, lalgorithme sach`eve toujours.
Proposition VI.6.7. Soit G = (V, , P, S) une grammaire essentiellement
monotone. Il existe une grammaire equivalente G
ne contenant aucune 1-
production. De plus, cette grammaire peut etre obtenue de mani`ere eective.
16
On utilise ici une approche top-down.
134 Chapitre VI. Introduction aux langages algebriques
Demonstration. Cela decoule immediatement de la constatation faite ` a
la remarque VI.6.5. Pour toute variable A qui est le premier membre dune
1-production, les r`egles de la nouvelle grammaire G
.)
Si A est une variable napparaissant dans aucun premier membre des 1-
productions de G, les r`egles correspondantes de G et de G
sont identiques.
Les variables, lalphabet des symboles terminaux et le symbole initial de
G
S [
S ACA [ CA [ AA [ AC [ A [ C
A aAa [ B [ C [ aa
B bB [ b
C cS [ c.
Les 1-productions sont S
S, S A, S C, A B et A C. Ainsi,
on trouve
((S
) = S
, S, A, B, C, ((S) = S, A, B, C et ((A) = A, B, C.
Par consequent, la nouvelle grammaire est
S
..
S
G
uxv
G
w
avec u, v (V )
et w
.
Pour eliminer les symboles inutiles, nous allons proceder en deux par-
ties. Tout dabord, nous detectons les variables permettant de generer des
mots formes de symboles terminaux. Lalgorithme est semblable ` a celui
determinant les symboles ea cables. Posons
T
0
= A V [ w
: A w P.
Pour i 0, on denit
T
i+1
= T
i
A V [ w (T
i
)
: A w P.
Puisque V est ni, la suite des T
i
se stabilise. Soit T, lensemble des variables
permettant dobtenir un mot sur . Si A nappartient pas ` a T, alors A est
inutile.
Proposition VI.6.11. Soit G = (V, , P, S) une grammaire. Avec les no-
tations introduites precedemment, il existe une grammaire equivalente G
ne
contenant que les variables de T. De plus, cette grammaire peut etre obtenue
de mani`ere eective.
Demonstration. Il sut de supprimer les r`egles faisant intervenir une
variable de V T. Ainsi, lensemble des variables de G
est T, lensemble
des productions de G
est
A w P [ A T, w (T )
uBv, u, v (V )
, et donc B ne contribue ` a
aucune derivation ` a partir de S. La seconde etape permettant deliminer les
symboles inutiles consiste ` a conserver uniquement les symboles accessibles.
Denition VI.6.13. Soit G = (V, , P, S) une grammaire hors contexte.
Une variable A est accessible si
S
uAv
avec u, v (V )
: C uBv.
La procedure sarrete lorsque A
i
= A
i+1
et lensemble obtenu est clairement
lensemble des variables accessibles.
Proposition VI.6.14. Soit G = (V, , P, S) une grammaire. Il existe une
grammaire equivalente G
mise
sous forme normale de Chomsky.
Demonstration. Au vu des sous-sections precedentes, on peut supposer
que Gest essentiellement monotone et quelle ne contient aucune 1-production
ni symbole inutile. Ainsi, une r`egle de la grammaire G est de lune des formes
suivantes :
S ,
A a o` u A V , a ,
A w o` u A V , w ((V ) S)
et [w[ 2.
Les deux premiers types de r`egles satisfont la forme de Chomsky. Il nous
reste ` a montrer comment remplacer le troisi`eme type de r`egles. Soit la r`egle
A w o` u
w = w
1
A
1
w
2
w
n
A
n
w
n+1
, avec w
i
, A
i
V S.
Si w
i
,= , on notera w
i
= w
i,1
w
i,
i
avec w
i,j
. Sans changer le langage
genere, on peut remplacer la r`egle A w par les r`egles
A W
1,1
W
1,
1
A
1
W
2,1
W
n,n
A
n
W
n+1,1
W
n+1,
n+1
W
1,1
w
1,1
.
.
.
W
n+1,
n+1
w
n+1,
n+1
o` u les W
i
sont de nouvelles variables. Il reste simplement ` a modier la
premi`ere de ces nouvelles r`egles pour avoir une grammaire mise sous forme
de Chomsky. Si une r`egle est de la forme
A A
1
A
n
, n 3,
en faisant intervenir de nouvelles variables, on peut la remplacer par les
r`egles
A A
1
B
1
B
1
A
2
B
2
.
.
.
B
n2
A
n1
A
n
.
S
S SaB [ aB [ Sa [ a
B bB [ b.
Ensuite, on supprime les 1-productions et on obtient
S
SaB [ aB [ Sa [ a
S SaB [ aB [ Sa [ a
B bB [ b
et on remarque quaucun symbole nest inutile. En introduisant de nouvelles
variables, on a tout dabord
S
SAB [ AB [ SA [ a
S SAB [ AB [ SA [ a
B B
B [ b
A a
B
b.
Enn, pour obtenir des r`egles de longueur au plus deux, on a
S
ST [ AB [ SA [ a
S ST [ AB [ SA [ a
B B
B [ b
A a
B
b
T AB.
6.5. Forme normale de Greibach.
Denition VI.6.20. Une grammaire hors contexte G = (V, , P, S) est
sous forme normale de Greibach si les r`egles de G sont toutes de lune des
formes suivantes :
A aA
1
A
n
avec A V , a , A
i
V S,
A a avec A V et a ,
S .
Linteret pratique de la mise sous forme normale de Greibach est qu` a
chaque derivation, on determine un prexe de plus en plus long forme unique-
ment de symboles terminaux. Cela permet de construire plus aisement des
analyseurs permettant de retrouver larbre danalyse associe ` a un mot genere.
Dans ce texte introductif, nous enon cons le resultat suivant.
Theor`eme VI.6.21.
18
Soit G = (V, , P, S) une grammaire hors contexte.
On peut construire de mani`ere eective une grammaire equivalente G
mise
sous forme normale de Greibach.
18
Le lecteur interesse trouvera par exemple plus de details dans T. A. Sudkamp,
Languages and Machines, An introduction to the Theory of Computer Science, 2e edition,
Addison-Wesley, (1998), pp. 140147.
140 Chapitre VI. Introduction aux langages algebriques
7. Lemme de la pompe
On dispose dun analogue du lemme de la pompe dans le cadre des
langages hors contexte.
Proposition VI.7.1 (Lemme de la pompe Theor`eme de Bar-Hillel). Soit
L un langage hors contexte. Il existe p N 0 tel que tout mot z L de
longueur [z[ p peut secrire z = uvwxy, u, v, w, x, y
w, w
, a un
arbre danalyse de hauteur n, alors [w[ 2
n1
.
Demonstration. Puisque la grammaire est mise sous forme normale de
Chomsky, les seuls arbres danalyse
19
de hauteur 1 dont le fruit est forme de
symboles terminaux sont de la forme donnee ` a la gure VI.9 et leurs fruits
a
A S
w avec w
et [w[ > 2
n1
19
A la section 2, on a suppose que les seconds membres des productions netaient ja-
mais egaux ` a . Ici, nous autorisons une telle situation. Il est clair que cette generalisation
ne modie en rien les developpements de la section 2.
VI.7. Lemme de la pompe 141
(donc en particulier, avec [w[ 2
n
), alors larbre danalyse associe ` a cette
derivation est de hauteur au moins n + 1.
Nous en arrivons ` a present ` a la preuve du lemme de la pompe.
Demonstration. Sans restriction, nous pouvons supposer que la grammaire
est mise sous forme normale de Chomsky. Posons #V = m. Soit z un
mot genere par G de longueur au moins 2
m
=: p. Au vu du corollaire
precedent, on dispose dun arbre danalyse de fruit z et de hauteur au moins
m + 1. Ainsi, cet arbre contient un chemin de longueur au moins m + 1
debutant en S et aboutissant en un symbole terminal. Une illustration de
cette situation est donnee ` a la gure VI.10. Ce chemin de longueur m + 1
a
S
0
1
4
3
2
Figure VI.10. Un arbre danalyse pour une grammaire sous
forme de Chomsky.
passe par m + 2 sommets de larbre dont m + 1 sont des variables. Or
#V = m. Par consequent, ce chemin contient au moins deux fois la meme
variable A. Dans ce chemin, nous considerons les 2 occurrences de A, le plus
bas possible dans larbre (i.e., le plus loin de la racine). Schematiquement,
dans larbre danalyse de z, on a la situation representee ` a la gure VI.11.
Ainsi, la grammaire contient les derivations
S
A
A
u v w x y
Figure VI.11. Un arbre danalyse avec A apparaissant deux fois.
142 Chapitre VI. Introduction aux langages algebriques
S
uAy, A
vAx et A
w.
Par consequent, en appliquant n fois la derivation centrale, on obtient
S
uAy
uvAxy
uv
n
Ax
n
y
uv
n
wx
n
y
et les mots uv
n
wx
n
y appartiennent ` a L(G) pour tout n N.
Pour terminer la demonstration du resultat, nous devons encore verier
que [vwx[ < p et vx ,= . Puisque la grammaire est sous forme de Chomsky,
la derivation A
vArC
vArs = vAx.
La variable C ne peut donner (en eet, seul S ). On en conclut que
x ,= et donc vx ,= . Le sous-arbre de racine A et de fruit vwx est de
hauteur au plus m (au vu du choix des deux occurrences de A prises le plus
bas possible). Par consequent, [vwx[ 2
m1
< p.
Ce resultat peut etre utilise pour montrer que certains langages ne sont
pas algebriques.
Exemple VI.7.4. Le langage
L = a
n
b
n
c
n
[ n N
nest pas algebrique. Procedons par labsurde. Soit p lentier donne dans
lenonce du lemme de la pompe. Le mot z = a
p
b
p
c
p
est de longueur au
moins p. Il existe donc des mots u, v, w, x, y tels que
a
p
b
p
c
p
= uvwxy
avec [vwx[ < p et vx ,= . Par consequent, vwx ne peut contenir simul-
tanement des lettres a, b et c. Ceci contredit le fait que uv
n
wx
n
y doive
appartenir au langage pour tout n.
7.1. Theor`eme de Parikh. Un autre resultat peut parfois saverer
utile pour verier quun langage nest pas algebrique. Nous ne ferons ici que
denoncer le theor`eme de Parikh.
Denition VI.7.5. Un sous-ensemble M de N
k
est dit lineaire sil existe
p
0
, p
1
, . . . , p
s
N
k
tels que
M = p
0
+
s
i=1
i
p
i
[
1
, . . . ,
s
N = p
0
+N.p
1
+ +N.p
s
.
On dit que p
0
est la constante de M et les p
i
s, i 1, en sont les periodes.
Une union nie densembles lineaires est un ensemble semi-lineaire.
Theor`eme VI.7.6 (Parikh). Si L
1
, . . . ,
k
est un langage algebrique,
alors (L) est un ensemble semi-lineaire de N
k
.
VI.8. Automates ` a pile 143
Remarque VI.7.7. La reciproque de ce resultat est fausse. En eet, nous
savons que le langage L = a
n
b
n
c
n
[ n N nest pas algebrique. Par contre,
(L) = N.
_
_
1
1
1
_
_
est semi-lineaire.
8. Automates `a pile
Dune part, nous avons vu dans les sections precedentes que les gram-
maires hors contexte etaient utilisees pour generer les langages algebriques.
Dune certaine fa con, les grammaires sont une generalisation des expressions
reguli`eres qui permettent quant ` a elles de generer les langages reguliers.
Dautre part, nous avons montre que les automates nis acceptent ex-
actement les langages reguliers. Lensemble des langages reguliers etant
un sous-ensemble strict de lensemble des langages algebriques, pour esperer
trouver lanalogue des automates nis, nous allons etendre les possibilites de
ces derniers par lajout dune pile. Un automate ni est, par denition, une
machine ne disposant que dune memoire nie (le nombre de congurations
qui peuvent etre memorisees est egal ` a son nombre detats). Lajout dune
pile
20
permet detendre les possibilites de memorisation, puisque, comme
nous allons le voir, la capacite de stockage dune pile peut etre arbitraire-
ment grande.
Une pile est un dispositif du type
21
dernier entre, premier sorti. On
a
b
c
Figure VI.12. Representation dune pile.
peut la representer ` a laide dun mot ni. Par convention, on notera lalphabet
de pile . Une pile est donc un mot p
, , w
, et
depiler un symbole est loperation
w
.
On peut etendre ces notions ` a des mots. Ainsi, empiler un mot u = u
1
u
. Partant de la pile w,
on obtient
w u
1
w u
2
u
1
w . . . u
u
1
w = u
R
w.
Remarque VI.8.1. Dans la suite, il faudra etre attentif ` a cette situation
faisant apparatre le miroir de u (cf., par exemple, la relation de transition
donnee dans la proposition VI.8.6).
Denition VI.8.2. Un automate ` a pile
22
est la donnee dun sextuple / =
(Q, , , , q
0
, F) o` u Q est un ensemble ni detats, est lalphabet de
lautomate, est lalphabet de pile,
Q
dont le r ole est de coder letat q dans lequel se trouve lautomate, le mot w
restant ` a lire et letat p de la pile. On passe de la conguration [q, w, p] ` a la
conguration [q
, w
, p
, p = xy, p
= z
R
y et (q, m, x, q
, z) .
En dautres termes, on a lu m, on a depile x et empile z. La representation
sagittale correspondante est donnee ` a la gure VI.13. Les autres conventions
q
m, x/z
q
Figure VI.13. Une transition dun automate ` a pile.
sont analogues ` a celles utilisees pour representer les automates nis. On
notera d`es lors cette transition par
[q, w, p] [q
, w
, p
]
22
Le mod`ele presente ici est non deterministe. Le lecteur ayant dej` a rencontre la no-
tion dautomate ni pourra sapercevoir quon est en presence dune relation de transition
et non dune fonction de transition.
VI.8. Automates ` a pile 145
et
[q, , ] avec q F.
Il est evident que le langage accepte par / est
L(/) = w
[ q F : [q
0
, w, ]
[q, , ].
Deux automates ` a pile sont equivalents sils acceptent le meme langage.
Exemple VI.8.3. Lautomate ` a pile represente ` a la gure VI.14 accepte
exactement le langage a
n
b
n
[ n N. La pile dalphabet A y est utilisee
b, A/
b, A/
a, /A
, v (V )
et
[f, u, S]
[f, , v],
alors il existe une derivation ` a gauche telle que
S
uv.
Nous prouvons ce resultat par recurrence sur le nombre m de transitions ` a
eectuer pour passer de [f, u, S] ` a [f, , v]. Si m = 0, alors u = et S = v
et il est clair que S
[f, , v] se decompose en
[f, u, S]
[f, r, Av
] [f, r, wv
]
. .
derni`ere application (,A/w
R
)
[f, , v]
o` u r est un suxe de u, i.e., u = u
de u et o` u wv
= rv car
pour lire r, puisquon applique uniquement des r`egles de la forme (, /),
il faut que wv
r, S]
[f, r, Av
] = [f, r, Av
]
et donc
[f, u
, S]
[f, , Av
].
Ayant dans ce dernier cas au plus t transitions, on peut appliquer lhypoth`ese
de recurrence : il existe une derivation ` a gauche
S
Av
.
23
En eet, on ne saurait appliquer la transition (, /) ` a la conguration [f, u, S]
puisquil faudrait depiler dune pile ne contenant que S.
VI.8. Automates ` a pile 147
Or u
appartient ` a
Av
wv
= u
rv = uv.
La reciproque est egalement vraie. Sil existe une derivation ` a gauche
S
uv avec u
et v (V )
, alors [f, u, S]
[f, , ].
Vu la premi`ere partie de la demonstration, il existe une derivation ` a gauche
telle que S
.
Par la deuxi`eme partie de la preuve, on a [f, x, S]
[f, , ]
o` u pour conclure, on applique des transitions (, /) pour lire et depiler yz.
et p
)q
Q,
q, , q) pour tout q Q.
Exemple VI.8.8. Reprenons lautomate ` a pile introduit dans lexemple
VI.8.3 dont les transitions sont
(1, a, , 1, A), (1, b, A, 2, ), (2, b, A, 2, ).
On y ajoute la transition (1, a, A, 1, AA) et on consid`ere la grammaire dont
les r`egles sont
VI.8. Automates ` a pile 149
S 1, , 2) [ 1, , 1)
1, , 1) a 1, A, 1) (1, a, , 1, A)
1, , 2) a 1, A, 2)
1, A, 1) b 2, , 1) (1, b, A, 2, )
1, A, 2) b 2, , 2)
2, A, 1) b 2, , 1) (2, b, A, 2, )
2, A, 2) b 2, , 2)
1, A, 1) a 1, A, 1) 1, A, 1) (1, a, A, 1, AA)
1, A, 1) a 1, A, 2) 2, A, 1)
1, A, 2) a 1, A, 1) 1, A, 2)
1, A, 2) a 1, A, 2) 2, A, 2)
1, , 1)
2, , 2)
(On a indique ` a chaque fois, de quelle transition provient la r`egle.) Le mot
aabb est accepte par lautomate car on a la suite de congurations
[1, aabb, ] [1, abb, A] [1, bb, AA] [2, b, A] [2, , ].
Ce mot est aussi genere par la grammaire en considerant la derivation
S 1, , 2) a1, A, 2) aa1, A, 2)2, A, 2) aab2, , 2)2, A, 2)
aab2, A, 2) aabb2, , 2) aabb.
Bien que cet exemple ne constitue en rien une preuve, on remarque que la
grammaire permet dune certaine fa con de tenir compte des lettres lues dans
lautomate et de retenir letat de la pile.
Le resultat suivant peut aussi etre considere comme une consequence du
theor`eme de Chomsky-Sch utzenberger (theor`eme VI.10.3). A la dierence de
ce dernier, la preuve donnee ici est constructive : on associe une grammaire
de mani`ere canonique ` a lautomate considere.
Proposition VI.8.9. Tout langage accepte par un automate ` a pile / est
hors contexte.
Demonstration. Nous supposons etre dans les conditions donnees ci-
dessus (i.e., nous disposons dun automate ` a pile / modie auquel on a
associe une grammaire G). Avec les notations qui prec`edent, nous devons
montrer que dans /, [q
0
, w, ]
w.
Montrons tout dabord que si [q
i
, w, A]
[q
j
, , ] avec A ,
alors il existe une derivation de G telle que q
i
, A, q
j
)
w. On proc`ede
par recurrence sur la longueur de la suite de congurations. Si celle-ci est
nulle, q
i
= q
j
, w = , A = et pour conclure, on remarque que q
i
, , q
i
)
est une r`egle de G. Supposons le resultat acquis pour une suite de longueur
n et verions-le pour une suite de longueur n + 1. Si [q
i
, w, A]
[q
j
, , ]
avec une suite de n + 1 transitions, alors on peut decomposer cette suite
150 Chapitre VI. Introduction aux langages algebriques
en lapplication dune premi`ere transition suivie par n autres. On a deux
possibilites. Tout dabord
[q
i
, w, A] [q
k
, v, B]
[q
j
, , ]
si w = sv et (q
i
, s, A, q
k
, B) , s . Par hypoth`ese de recurrence,
on a q
k
, B, q
j
)
v. De plus, ` a la transition (q
i
, s, A, q
k
, B) correspond
notamment la r`egle q
i
, A, q
j
) sq
k
, B, q
j
). Ainsi,
q
i
, A, q
j
) sq
k
, B, q
j
)
sv = w.
Lautre situation ` a envisager est
[q
i
, w, A] [q
k
, v, BA]
[q
, y, A]
[q
j
, , ]
o` u la premi`ere transition est de la forme (q
i
, s, A, q
k
, AB), s et w =
sv, v = xy. La grammaire contient la r`egle q
i
, A, q
j
) sq
k
, B, q
)q
, A, q
j
).
Puisque [q
k
, v, BA]
[q
[q
x et q
, A, q
j
)
y.
Do` u
q
i
, A, q
j
) sq
k
, B, q
)q
, A, q
j
)
sxy = w.
De l` a, on en conclut aisement que L(/) L(G).
Montrons ` a present que si q
i
, A, q
j
)
w, w
, A ,
alors [q
i
, w, A]
[q
j
, , ]. On proc`ede une fois encore par recurrence sur
la longueur de la derivation. Sil sagit dune derivation de longueur un,
les seules r`egles de la grammaire donnant un symbole terminal sont de la
forme q, , q) et on a bien [q
i
, , ]
[q
i
, , ]. Supposons ` a present la
propriete satisfaite pour les derivations de longueur au plus n et demontrons-
la pour les derivations de longueur n + 1. Si la premi`ere r`egle appliquee est
de la forme q
i
, A, q
j
) sq
k
, B, q
j
), alors on a
q
i
, A, q
j
) sq
k
, B, q
j
)
sv = w.
Par hypoth`ese de recurrence, [q
k
, v, B]
[q
j
, , ]. De plus, par construction
de G, la r`egle q
i
, A, q
j
) sq
k
, B, q
j
) provient de la transition (q
i
, s, A, q
k
, B)
et [q
i
, sv, A] [q
k
, v, B]. La seconde possibilite est que la premi`ere r`egle ap-
pliquee soit de la forme q
i
, A, q
j
) sq
k
, B, q
m
)q
m
, A, q
j
). Dans ce cas, on
a
q
i
, A, q
j
) sq
k
, B, q
m
)q
m
, A, q
j
)
w
avec
q
k
, B, q
m
)
x, q
m
, A, q
j
)
y et w = sxy.
On conclut en appliquant deux fois lhypoth`ese de recurrence. D`es lors,
L(G) L(/) et ceci termine la preuve.
Remarque VI.8.11. Dans le cadre des langages reguliers, nous avons mon-
tre que les ensembles des langages acceptes par automate ni deterministe ou
non deterministe concident. Ainsi, le caract`ere non deterministe napporte
rien du point de vue des langages acceptes (il apporte neanmoins des facil-
ites de construction non negligeables). On peut naturellement se poser la
meme question dans le cas des langages algebriques. On peut montrer
25
que
la classe des langages acceptes par un automate ` a pile deterministe est un
sous-ensemble strict des langages algebriques. Il sagit des langages prexes.
Un langage L
est prexe si
u, v
: u L, uv L v = .
Autrement dit, si un mot u est dans L, aucun prexe propre de u nappartient
` a L.
9. Stabilite du caract`ere algebrique
Nous avons vu precedemment que lensemble des langages algebriques
etait stable pour lunion, la concatenation et letoile de Kleene. Nous allons
montrer ici que lintersection de deux langages algebriques nest en general
pas algebrique. Par consequent, le complementaire dun langage algebrique
nest en general pas algebrique. Neanmoins, lintersection dun langage al-
gebrique et dun langage regulier est encore algebrique.
Exemple VI.9.1. Le langage L = a
n
b
n
[ n Nc
b
n
c
n
[ n N est aussi
algebrique. Il est clair que
L M = a
n
b
n
c
n
[ n N
nest pas algebrique. Ainsi, cet exemple montre que lensemble des langages
algebriques nest pas stable pour lintersection.
Remarque VI.9.2. Supposons que pour tout langage L
, L algebrique
entrane
((
L) (
M)),
on pourrait en conclure que lintersection de deux langages algebriques est
encore algebrique (en eet, nous savons que lunion de deux langages al-
gebriques est algebrique, cf. proposition VI.4.2). Ainsi, lensemble des lan-
gages algebriques ne peut pas etre stable pour le passage au complementaire.
25
Voir par exemple, J.-M. Autebert, Langages Algebriques, etudes et recherche en
informatique, Masson, Paris, (1987).
152 Chapitre VI. Introduction aux langages algebriques
Theor`eme VI.9.3. Soient R
un langage regulier et L
un
langage algebrique. Le langage L R est algebrique.
Demonstration. Lidee de la demonstration consiste, tout comme dans
le cas de lintersection de deux langages reguliers, ` a construire un auto-
mate produit simulant simultanement le comportement dun automate ni
deterministe acceptant R et dun automate ` a pile acceptant L. Soient
/ = (Q, q
0
, F, , ) et /
= (Q
, , ,
, q
0
, F
, , , , (q
0
, q
0
), F F
)
o` u la relation de transition est donnee par
((q
i
, q
i
), , x, (q
j
, q
j
), y) si (q
i
, ) = q
j
et (q
i
, , x, q
j
, y)
et
((q
i
, q
i
), , x, (q
i
, q
j
), y) si (q
i
, , x, q
j
, y)
.
Il est facile de se convaincre que le langage accepte par T est exactement
L R. On conclut en utilisant la proposition VI.8.9.
Lemme VI.9.4. Lensemble des langages algebriques est stable par mor-
phisme.
Demonstration. Soient L
= (V , , P
, S) o` u
P
= P h() [ .
Il est clair que cette nouvelle grammaire gen`ere le langage h(L).
o` u e
1
, . . . , e
k
, d
1
, . . . , d
k
sont de nouveaux symboles
27
. Si p
represente
letat de la pile, les elements de agissent sur p comme suit :
26
Il faut surtout ne pouvoir lire quau plus une lettre de ` a chaque transition.
27
e comme empilement et d comme depilement
VI.10. Un theor`eme de Sch utzenberger 153
, .p = p,
i 1, . . . , k, e
i
.p =
i
p,
si p =
i
p
, alors d
i
.p = p
.
Si x = x
1
x
n
, on a x.p = x
1
.( (x
n1
.(x
n
.p)) ) pour autant
que ces operations puissent etre denies
28
. En particulier, xy.p = x.(y.p),
x, y
.
Denition VI.10.1. Avec les notations qui prec`edent, on introduit le lan-
gage D
A
forme des mots qui transforment la pile vide en elle-meme, i.e.,
D
A
= x
[ x. = .
Proposition VI.10.2. Le langage D
A
est algebrique et genere par la gram-
maire dont les r`egles sont donnees par
S Sd
1
Se
1
S [ [ Sd
k
Se
k
S [
1
S [ [
m
S [ .
Demonstration. Soit w D
A
. Montrons que S
w par recurrence
sur [w[. Si w = , le resultat est satisfait. Supposons le resultat acquis
pour les mots de longueur au plus et verions-le pour les mots de longueur
+1. Si w
+1
, le resultat est immediat. Il sut dappliquer +1 r`egles
S
t
S. Nous pouvons donc supposer que w contient un symbole e
i
(que
nous prenons le plus ` a droite possible dans w), i.e.,
w = ue
i
z, avec u
, z
.
Il est clair que z ne contient pas de symbole e
j
(par choix de e
i
), mais il ne
peut non plus contenir des symboles d
j
(car w ne denirait pas une action
valide). De plus, ` a ce symbole e
i
realisant lempilement de
i
, il correspond
exactement un symbole d
i
le depilant (car w D
A
). Ainsi, on a
w = xd
i
ye
i
z, avec x, y
.
De l` a, on tire que x, y et z appartiennent ` a D
A
. En appliquant trois fois
lhypoth`ese de recurrence, on a S
x, S
y, S
z. On conclut en
remarquant que S Sd
i
Se
i
S
xd
i
ye
i
z = w.
Passons ` a la reciproque et verions que si S
w, w
, alors w
appartient ` a D
A
. Pour tout p
de
` a ( S)
w, w ( S)
, alors w.p = p
pour tout p
w
1
Sw
2
w.
28
Par exemple, d2e1.p nest jamais deni et ce, quel que soit p. En eet, e1 empile 1
et on devrait ensuite depiler e2 qui ne se trouve pas au sommet de la pile.
154 Chapitre VI. Introduction aux langages algebriques
Si la derni`ere r`egle appliquee est de la forme S Sd
i
Se
i
S, alors w =
w
1
Sd
i
Se
i
Sw
2
et pour tout p
, on a
w
1
Sd
i
Se
i
Sw
2
.p = w
1
Sd
i
Se
i
S.(w
2
.p) = w
1
Sd
i
Se
i
.(w
2
.p)
= w
1
Sd
i
S.(
i
(w
2
.p)) = w
1
Sd
i
.(
i
(w
2
.p)) = w
1
S.(w
2
.p)
= (w
1
Sw
2
).p = p
o` u, ` a la derni`ere ligne, on a applique lhypoth`ese de recurrence. Si la derni`ere
r`egle appliquee est de la forme S
i
S, alors w = w
1
i
Sw
2
et pour tout
p
,
w
1
i
Sw
2
.p = w
1
i
S.(w
2
.p) = w
1
i
.(w
2
.p) = w
1
.(w
2
.p) = (w
1
Sw
2
).p = p.
Enn, si la derni`ere r`egle appliquee est de la forme S , w = w
1
w
2
et
pour tout p
,
w
1
w
2
.p = (w
1
Sw
2
).p = p.
Ceci conclut la preuve.
et un langage regulier R
tel que
L = h(D
R
A
R).
En particulier, L est algebrique.
Demonstration. Puisque nous supposons / elementaire, on peut voir cet
automate comme un automate ni sur lalphabet . En eet, il sut de
remplacer les transitions par des arcs de label appartenant ` a :
(p, , , q, ) devient p
q,
(p,
i
, , q, ) devient p
i
q,
(p, ,
i
, q, ) devient p
e
i
q,
(p, , , q,
i
) devient p
d
i
q.
Par le theor`eme de Kleene, le langage R
[q, , ], avec q F.
A ce mot, il correspond donc un chemin dans / de label W
debutant
en q
0
et aboutissant en q F. Puisque, pour etre accepte par lautomate,
la suite de congurations debute et se nit par une pile vide, il est clair
que W
R
appartient ` a D
A
. De plus, W appartient ` a R. On retrouve w en
appliquant ` a W le morphisme
h :
:
_
_
_
i
i
e
i
d
i
.
VI.11. Exercices 155
Ce morphisme est simplement deni pour eacer les lettres de . Re-
ciproquement, si W
appartient ` a D
R
A
R, alors on se convainc aisement
que h(W) est un mot accepte par lautomate.
(b d
A
)
.
De plus, D
A
= d
n
A
e
n
A
[ n N. Ce langage est genere par la grammaire
S [ d
A
Se
A
.
Par exemple, le mot a e
A
a e
A
b d
A
appartient ` a R mais nappartient pas ` a
D
R
A
car le mot miroir d
A
b e
A
a e
A
a ne transforme pas la pile vide en la
pile vide, en eet: d
A
b e
A
a e
A
a. = A. Ainsi, a e
A
a e
A
b d
A
nappartient
pas ` a D
A
R. Par contre, le mot a e
A
b d
A
appartient ` a R et ` a D
R
A
car
d
A
b e
A
a. = . Si on lui applique le morphisme h, on trouve
h(a e
A
b d
A
) = ab
qui est bien un mot du langage.
11. Exercices
Exercice VI.11.1. Determiner une grammaire hors contexte generant les
langages
L = ww
R
[ w a, b
et
M = wcw
R
[ w a, b
.
Exercice VI.11.2. Decrire une grammaire hors contexte generant les lan-
gages
a
n
b
n
c
m
[ n, m N,
a
n
b
m
c
m
[ n, m N
et
a
n
b
m
[ m > n 0.
156 Chapitre VI. Introduction aux langages algebriques
Exercice VI.11.3. Le langage a
i
b
j
c
k
[ i ,= j ou i ,= k est-il algebrique ?
Justier votre reponse.
Exercice VI.11.4. Le langage
L = w a, b, c
: [w[
a
= [w[
b
= [w[
c
est-il algebrique ?
Exercice VI.11.7. Le langage forme des mots comprenant deux fois plus
de a que de b est-il algebrique ? Meme question avec le langage
L = w a, b
: [w[
a
= 2[w[
b
+ 3.
Exercice VI.11.8. Le langage des palindromes est-il algebrique ? Justi-
er. Meme question en considerant uniquement les palindromes de longueur
paire.
Exercice VI.11.9. Donnez la description dun automate ` a pile determin-
iste acceptant le langage
wcw
R
[ w a, b
.
Exercice VI.11.10. Decrire un automate ` a pile acceptant le langage forme
des palindromes sur lalphabet a, b. Meme question en considerant unique-
ment les palindromes de longueur paire.
Exercice VI.11.11. Quels sont les langages acceptes respectivement par
les automates ` a pile suivants
Exercice VI.11.12. Decrire un automate ` a pile acceptant le langage L
forme des mots sur a, b pour lesquels il existe un prexe contenant (stricte-
ment) plus de b que de a, i.e.,
u, v a, b
: w = uv et [u[
b
> [u[
a
.
Par exemple, baa, abba et abbaaa appartiennent ` a L mais aab et ababab ny
appartiennent pas.
VI.11. Exercices 157
a, /AAA
b, A/
b, A/
a, /AAA
b, A/
b, A/
a, /AAA
b, A/
Figure VI.17. Automates ` a pile.
Exercice VI.11.13. Montrer que si lautomate ` a pile / = (Q, , , , q
0
, F)
est elementaire alors les langages
G
p,q
= x
[ m
: [p, m, x]
[q, , ], p, q Q
sont reguliers. (Suggestion : exprimer t
1
.G
p,q
` a laide des dierents lan-
gages G
r,s
, t
.)
Exercice VI.11.14. Utiliser le lemme de la pompe pour montrer que les
langages suivants ne sont pas algebriques
a
k
2
[ k N
a
i
b
j
c
i
d
j
[ i, j 0
Lensemble des prexes de longueur nie du mot inni
abaabaaab ba
n
ba
n+1
b
Exercice VI.11.15. Les langages suivants sont-ils algebriques ?
L = a
i
b
2i
c
j
[ i, j 0,
M = a
j
b
i
c
2i
[ i, j 0
et
L M.
Exercice VI.11.16. Soit le langage
L = ww [ w a, b
.
Montrer que a, b
.
Meme question avec le langage
w
3
[ w a, b
.
Bibliographie
[1] A. Aho, J. Ullman, Concepts fondamentaux de linformatique, Dunod, Paris, (1993).
[2] A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools, Addison-
Wesley, (1986).
[3] J.-P. Allouche, J. Shallit, Automatic Sequences, Theory, Applications, Generaliza-
tions, Cambridge University Press, Cambridge, (2003).
[4] J.-P. Allouche, J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences
and their applications (Singapore, 1998), 116, Springer Ser. Discrete Math. Theor.
Comput. Sci., Springer, London, 1999.
[5] J.-M. Autebert, Langages algebriques, etudes et recherches en informatique, Masson,
Paris, (1987).
[6] J.-M. Autebert, J. Berstel, L. Boasson, Context-Free Languages and Pushdown Au-
tomata, Handbook of Formal Languagues, Vol. 1, Springer, (1997).
[7] E. Bach, J. Shallit, Algorithmic number theory, Ecient algorithms, Foundations of
Computing Series, MIT Press, Cambridge, MA, (1996).
[8] J. Berstel, L. Boasson, The set of minimal words of a context-free language is context-
free, J. Comput. System Sci. 55 (1997), 477488
[9] J. Berstel, C. Reutenauer, Les series rationnelles et leurs langages,
Etudes et
Recherches en Informatique, Masson, Paris, (1984).
[10] J. Berstel, D. Perrin, The origins of combinatorics on words, European J. Combin.
28 (2007), 9961022.
[11] V. Berthe, Combinatoire des mots, cours de DEA, Univ. Montpellier II (2006).
[12] V. Bruy`ere, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of
integers, Journees Montoises (Mons, 1992), Bull. Belg. Math. Soc. 1 (1994), 191238.
[13] J. H. Conway, Regular Algebra and Finite Machines, Mathematics Series, Chapman
and Hall, London, (1971).
[14] Ding-Zhu Du, Ker-I Ko, Problem solving in Automata, Languages, And Complexity,
John Wiley & Sons, (2001).
[15] S. Eilenberg, Automata, Languages, and Machines, Vol A., Academic Press, New
York-London, (1974).
[16] S. Eilenberg, Automata, Languages, and Machines, Vol B., Academic Press, New
York-London, (1976).
[17] B. Khoussainov, A. Nerode, Automata Theory and its Applications, Progress in Com-
puter Science and Applied Logic, Vol. 21, Birkhauser, Boston, (2003).
[18] M. V. Lawson, Finite Automata, Chapman & Hall/CRC Press, (2003).
[19] P. Lecomte, Algorithmitique et Calculabilite, notes de cours, Universite de Li`ege, 1996.
[20] P. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput.
Syst. 34 (2001), 2744
[21] M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge
University Press, Cambridge, 1997.
[22] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and
its Applications 90, Cambridge University Press, Cambridge, (2002).
[23] A. Mateescu, A. Salomaa, Formal Languages: an Introduction and a Synopsis, Hand-
book of Formal Languagues, vol. 1, Springer, (1997).
159
160 Chapitre VI. Bibliographie
[24] D. Perrin, Finite Automata, Handbook of Theoretical Computer Science, J. van
Leeuwen Ed., Elsevier, (1990), 357.
[25] D. Perrin, Les debuts de la theorie des automates, Technique et Science Informatique
14 (1995), 409433.
[26] M. Rigo, Automates et numeration, Bull. Soc. Royale Sci. Li`ege 74 (2005), 249262.
[27] J. Sakarovitch,
Elements de theorie des automates, Vuibert, Paris, (2003).
[28] A. Salomaa, Theory of Automata, International series of monograps on pure and
applied mathematics, Pergamon Press, Oxford, (1969).
[29] J. Shallit, Numeration systems, linear recurrences, and regular sets, Information and
Computation 113 (1994), 331347.
[30] T. A. Sudkamp, Languages and Machines, An Introduction to the Theory of Computer
Science, second edition, Addison-Wesley, Massachusetts, (1997).
[31] A. Szilard, S. Yu, K. Zhang, J. Shallit, Characterizing regular languages with poly-
nomial densities, MFCS 1992, Lect. Notes in Comput. Sci. 629, 494503, Springer,
(1992).
[32] W. Thomas, Automata on innite objects, in Handbook of theoretical computer sci-
ence, Vol. B, 133191, Elsevier, Amsterdam, 1990.
[33] S. Yu, Regular Languages, Handbook of Formal Languagues, vol. 1, Springer, (1997).
[34] P. Wolper, Introduction ` a la calculabilite, InterEditions, Paris, (1991).
Liste des gures
I.1 uv = vu. 5
I.2 xy = yz, [x[ [y[. 6
I.3 xy = yz, [x[ < [y[. 6
I.4 Preperiode et periode. 20
II.1 Un AFD. 28
II.2 Un automate ni deterministe. 29
II.3 Un AFND. 30
II.4 Un AFND avec -transitions. 31
II.5 Un AFND non elementaire /. 32
II.6 Un AFND elementaire equivalent ` a /. 32
II.7 Un automate non elementaire. 34
II.8 Un automate ni non deterministe. 35
II.9 AFD equivalent ` a lAFND de la gure II.8. 35
II.10 un ANFD acceptant a(ba)
. 36
II.11 un AFD acceptant a(ba)
. 37
II.12 Lautomate /
3
. 37
II.13 Un AFD acceptant L
3
. 38
II.14 Un AFD sur un alphabet unaire. 38
II.15 Representation symbolique dun automate. 39
II.16 Considerer un unique etat initial nest pas une restriction. 40
II.17 Automate acceptant L(/) L(B). 40
II.18 Automate acceptant L(/)L(B). 41
II.19 Automate acceptant (L(/))
. 41
II.20 Un AFND acceptant a(ba)
. 42
II.21 AFD acceptant a
et (cd)
. 45
II.22 AFD shue. 46
II.23 Deux automates nis deterministes. 47
II.24 Un AFND. 47
II.25 Un AFND ` a rendre deterministe. 48
161
162 Liste des gures
II.26 Un AFND. 48
III.1 AFD et AFND acceptant . 51
III.2 AFD et AFND acceptant . 51
III.3 AFD et AFND acceptant . 51
III.4 AFND acceptant a et b. 52
III.5 AFND acceptant a
. 52
III.6 AFND equivalent acceptant a
. 52
III.7 AFND acceptant a
b. 52
III.8 AFND acceptant a
ba
b. 53
III.9 AFND equivalent acceptant a
ba
b. 53
III.10 AFND acceptant (a
ba
b)
. 53
III.11 AFND acceptant (a
ba
b)
. 53
III.12 Un automate ni etendu (AFE). 54
III.13 Le pivotage. 55
III.14 Un AFE avant elimination de letat 2. 55
III.15 AFE equivalent apr`es elimination de letat 2. 56
III.16 AFE equivalent apr`es elimination de letat 3. 57
III.17 Le lemme de la pompe. 59
III.18 Expression reguli`ere du langage accepte. 62
III.19 Expression reguli`ere du langage accepte. 62
IV.1 Trois AFD equivalents. 63
IV.2 q
1
.F = w
1
.L si (q
0
, w) = q. 65
IV.3 Un automate minimal. 68
IV.4 Lautomate minimal dun langage non regulier. 68
IV.5 Une application satisfaisant les proprietes du theor`eme
IV.3.8. 69
IV.6 Un AFD dont on recherche les etats equivalents pour
A
. 73
IV.7 Un automate minimal. 74
IV.8 Un AFD accessible /. 74
IV.9 Un AFD /. 76
IV.10 Lautomate /
R
. 76
IV.11 Lautomate (/). 77
IV.12 Lautomate ((/))
R
. 77
IV.13 Lautomate ((/)). 77
IV.14 Un AFD. 81
Liste des gures 163
IV.15 Un autre AFD. 82
IV.16 Un autre AFD dont on cherche le minimal. 83
IV.17 Recherche des etats equivalents. 83
V.1 Un transducteur. 85
V.2 Un transducteur calculant le morphisme f. 86
V.3 wv appartient ` a
u. 89
V.4 Un automate detectant abbab. 91
V.5 Un automate detectant agata. 91
V.6 Un automate detectant ananas. 92
V.7 AFD acceptant les mots ne contenant pas aa. 92
V.8 Chemins de longueur n + 1 joignant q ` a r. 93
V.9 Projection : Q Q
L
sur /
L
. 98
V.10 Situation dans lautomate minimal. 101
V.11 Situation dans lautomate minimal. 102
V.12 AFD acceptant les mots ne contenant pas aa. 103
V.13 Graphe associe ` a H
L
. 103
V.14 Automate minimal de L = w :[ [w[
a
[w[
b
0
(mod 2). 104
V.15 Indice et periode. 106
V.16 Un AFD dont on recherche le monode syntaxique du
langage associe. 111
V.17 Un AFD dont on recherche le monode syntaxique. 111
V.18 Deux AFD. 112
V.19 Un AFD. 112
VI.1 Un arbre. 119
VI.2 Des arbres danalyse. 120
VI.3 Arbres danalyse provenant de derivations. 121
VI.4 Un arbre danalyse. 122
VI.5 Un arbre danalyse pour 1 2 + 3. 123
VI.6 Un arbre danalyse pour 1 2 + 3. 124
VI.7 Deux arbres danalyse pour 2 + 3 5. 125
VI.8 Arbres danalyse de 1 2 + 3 et 2 + 3 5 pour une
grammaire non ambigue. 125
VI.9 Arbres danalyse de hauteur 1 pour une grammaire mise
sous forme normale de Chomsky. 140
VI.10 Un arbre danalyse pour une grammaire sous forme de
Chomsky. 141
164 Liste des gures
VI.11 Un arbre danalyse avec A apparaissant deux fois. 141
VI.12 Representation dune pile. 143
VI.13 Une transition dun automate ` a pile. 144
VI.14 Un automate ` a pile acceptant a
n
b
n
[ n N. 145
VI.15 Automate acceptant L(G). 146
VI.16 Automate elementaire acceptant a
n
b
n
[ n N. 155
VI.17 Automates ` a pile. 157
Index
Notations
D
A
(pile vide) . . . . . . . . . . . . . . . . . . . 153
D
L (derive) . . . . . . . . . . . . . . . . . . . . . 66
E
u
(p) (recherche dun mot) . . . . . . . 89
F (etats nals) . . . . . . . . . . . . . . . . 27, 29
L
(etoile de Kleene) . . . . . . . . . . . . . 12
L
+
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
L
n
(puissance) . . . . . . . . . . . . . . . . . . . 11
Q (etats) . . . . . . . . . . . . . . . . . . . . . . 27, 29
S
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
A
L
(automate minimal) . . . . . . . . . . 66
(relation de transition) . . . . . . . . . 29
(fonction de transition) . . . . . . . . . 27
L
(congruence syntaxique) . . . . . . 99
C
a
(sous-groupe). . . . . . . . . . . . . . . . .106
H
L
(monode des transitions) . . . . 102
Com(L) (cl oture commutative) . . . . 14
Pal(
) (palindromes). . . . . . . . . . . . 11
(A) (determinise de A
R
) . . . . . . . . 75
2
(valeur base 2) . . . . . . . . . . . . . . . . 50
(fonction de Parikh) . . . . . . . . . . . . . 2
L
(complexite) . . . . . . . . . . . . . . . 46, 92
(shue) . . . . . . . . . . . . . . . . . . . . . . 15
L
(congruence de Nerode) . . . . . . . 64
k
(nombre de lettres) . . . . . . . . . . . 1
q
1
.G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
q
0
(etat initial) . . . . . . . . . . . . . . . . . . . 27
w
R
(miroir). . . . . . . . . . . . . . . . . . . . . . . . 8
w
1
.L. . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Rat(
) . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Fac(L) . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Fac(w) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Pref(L). . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Pref(w). . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Su(L) . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Su(w) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
A
adjacence (matrice) . . . . . . . . . . . . . . . 92
AFD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
AFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
AFND. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
algorithme
1-production . . . . . . . . . . . . . . . . . . 133
etats equivalents . . . . . . . . . . . . . . . 72
constr. par sous-ensembles . . . . . 34
McNaughton-Yamada . . . . . . . . . . 56
obtention expression reguli`ere . . 56
semi-groupe aperiodique. . . . . . . 108
symboles inutiles . . . . . . . . . . . . . . 135
variables ea cables . . . . . . . . . . . . 131
alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
ancetre . . . . . . . . . . . . . . . . . . . . . . . . . . 119
arbre danalyse . . . . . . . . . . . . . . . . . . 119
fruit . . . . . . . . . . . . . . . . . . . . . . . . . . 120
automate
emonde . . . . . . . . . . . . . . . . . . . . . . . . 95
` a pile . . . . . . . . . . . . . . . . . . . . . . . . . 144
elementaire . . . . . . . . . . . . . . . . . 145
atomique . . . . . . . . . . . . . . . . . . . 145
conguration . . . . . . . . . . . . . . . 144
determinsite . . . . . . . . . . . . . . . . 145
equivalent . . . . . . . . . . . . . . . . . . 145
accessible . . . . . . . . . . . . . . . . . . . . . . 69
complet . . . . . . . . . . . . . . . . . . . . . . . . 27
elementaire. . . . . . . . . . . . . . . . . . . . . 31
equivalent. . . . . . . . . . . . . . . . . . . 30, 54
ni deterministe . . . . . . . . . . . . . . . . 27
165
166 Index
ni etendu . . . . . . . . . . . . . . . . . . . . . 54
ni non deterministe . . . . . . . . . . . 29
minimal . . . . . . . . . . . . . . . . . . . . . . . . 66
reduit . . . . . . . . . . . . . . . . . . . . . . . . . . 69
sans permutation. . . . . . . . . . . . . . 112
B
Bar-Hillel (theor`eme de) . . . . . . . . . 140
C
chevauchement . . . . . . . . . . . . . . . . . . . . 8
Chomsky
-Sch utzenberger (theor`eme) . . . 154
forme normale . . . . . . . . . . . . . . . . 137
hierarchie (de) . . . . . . . . . . . . . . . . 129
cl oture rationnelle . . . . . . . . . . . . . . . . 22
cl oture commutative . . . . . . . . . . . . . . 14
code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
combinatoire des mots . . . . . . . . . . . . . 4
complexite. . . . . . . . . . . . . . . . . . . . . . . . 92
congruence syntaxique . . . . . . . . . . . . 99
constante. . . . . . . . . . . . . . . . . . . . . . . . 142
D
depiler . . . . . . . . . . . . . . . . . . . . . . . . . . 144
derivation . . . . . . . . . . . . . . . . . . . . . . . 116
` a gauche . . . . . . . . . . . . . . . . . . . . . . 117
` a droite . . . . . . . . . . . . . . . . . . . . . . . 117
descendant . . . . . . . . . . . . . . . . . . . . . . 119
distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
non-archimedienne . . . . . . . . . . . . . . 4
ultrametrique . . . . . . . . . . . . . . . . . . . 4
Dyck (langage de) . . . . . . . . . . . . . . . 118
E
empiler . . . . . . . . . . . . . . . . . . . . . . . . . . 144
ensemble
lineaire. . . . . . . . . . . . . . . . . . . . . . . . 142
semi-lineaire . . . . . . . . . . . . . . . . . . 142
ultimement periodique . . . . . . . . . 20
etat . . . . . . . . . . . . . . . . . . . . . . . . . . . 27, 29
accessible . . . . . . . . . . . . . . . . . . . . . . 43
coaccessible . . . . . . . . . . . . . . . . . . . . 43
nal . . . . . . . . . . . . . . . . . . . . . . . . 27, 29
initial . . . . . . . . . . . . . . . . . . . . . . . 27, 29
etoile (lemme) . . . . . . . . . . . . . . . . . . . . 58
etoile de Kleene . . . . . . . . . . . . . . . . . . 12
expression reguli`ere . . . . . . . . . . . . . . . 16
equivalente . . . . . . . . . . . . . . . . . . . . . 16
sans etoile. . . . . . . . . . . . . . . . . . . . . 105
F
facteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
propre. . . . . . . . . . . . . . . . . . . . . . . . . . . 2
factoriel (langage) . . . . . . . . . . . . . . . . 14
ls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
fonction
complexite (de) . . . . . . . . . . . . . . . . 92
Parikh (de). . . . . . . . . . . . . . . . . . . . . . 2
rationnelle . . . . . . . . . . . . . . . . . . . . . 85
transition . . . . . . . . . . . . . . . . . . . . . . 27
G
grammaire
equivalente . . . . . . . . . . . . . . . . . . . . 116
algebrique. . . . . . . . . . . . . . . . . . . . . 116
dependant du contexte . . . . . . . . 128
hors contexte . . . . . . . . . . . . . . . . . 116
lineaire. . . . . . . . . . . . . . . . . . . . . . . . 128
monotone . . . . . . . . . . . . . . . . . . . . . 129
non contractante . . . . . . . . . . . . . . 129
non ambigue . . . . . . . . . . . . . . . . . . 117
non restrictive . . . . . . . . . . . . . . . . 128
production . . . . . . . . . . . . . . . . . . . . 116
reguli`ere . . . . . . . . . . . . . . . . . . . . . . 127
r`egle de derivation . . . . . . . . . . . . 116
symbole
non terminal . . . . . . . . . . . . . . . . 116
terminal . . . . . . . . . . . . . . . . . . . . 116
symbole initial . . . . . . . . . . . . . . . . 116
variable . . . . . . . . . . . . . . . . . . . . . . . 116
Greibach
forme normale . . . . . . . . . . . . . . . . 139
I
inevitable. . . . . . . . . . . . . . . . . . . . . . . . . . 4
indice . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
K
Kleene
etoile. . . . . . . . . . . . . . . . . . . . . . . . . . . 12
theor`eme (de) . . . . . . . . . . . . . . . . . . 57
L
langage . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
accepte . . . . . . . . . . . . . . . . . 28, 30, 54
algebrique. . . . . . . . . . . . . . . . . . . . . 116
Index 167
commutatif . . . . . . . . . . . . . . . . . . . . . 15
concatenation . . . . . . . . . . . . . . . . . . 11
Dyck. . . . . . . . . . . . . . . . . . . . . . . . . . 118
etoile. . . . . . . . . . . . . . . . . . . . . . . . . . . 12
factoriel . . . . . . . . . . . . . . . . . . . . . . . . 14
hors contexte . . . . . . . . . . . . . . . . . 116
image inverse par morphisme . . . 14
image par morphisme . . . . . . . . . . 14
miroir . . . . . . . . . . . . . . . . . . . . . . . . . . 14
non ambigu . . . . . . . . . . . . . . . . . . . 117
prexe . . . . . . . . . . . . . . . . . . . . . . . . 151
prexiel . . . . . . . . . . . . . . . . . . . . . . . . 14
puissance. . . . . . . . . . . . . . . . . . . . . . . 11
regulier . . . . . . . . . . . . . . . . . . . . . . . . 16
racine k-i`eme. . . . . . . . . . . . . . . . . . . 79
rationnel . . . . . . . . . . . . . . . . . . . . . . . 21
sans etoile. . . . . . . . . . . . . . . . . . . . .105
shue. . . . . . . . . . . . . . . . . . . . . . . . . . 15
suxiel . . . . . . . . . . . . . . . . . . . . . . . . 14
lettre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . 142
M
matrice (adjacence) . . . . . . . . . . . . . . . 92
McNaughton-Yamada
algorithme. . . . . . . . . . . . . . . . . . . . . . 56
miroir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
monode syntaxique . . . . . . . . . . . . . 101
morphisme . . . . . . . . . . . . . . . . . . . . . . . . 3
ea cant . . . . . . . . . . . . . . . . . . . . . . . . 14
non ea cant . . . . . . . . . . . . . . . . . . . . 14
mot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
concatenation . . . . . . . . . . . . . . . . . . . 3
constant. . . . . . . . . . . . . . . . . . . . . . . . . 7
inni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
longueur . . . . . . . . . . . . . . . . . . . . . . . . 1
periode . . . . . . . . . . . . . . . . . . . . . . . . . . 6
primitif . . . . . . . . . . . . . . . . . . . . . . . . 24
vide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Myhill-Nerode (theor`eme de) . . . . . 71
N
Nerode (congruence). . . . . . . . . . . . . . 64
O
operation rationnelle. . . . . . . . . . . . . . 21
P
periode . . . . . . . . . . . . . . . 6, 20, 107, 142
p`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
palindrome . . . . . . . . . . . . . . . . . . . . . . . . 8
Parikh
fonction . . . . . . . . . . . . . . . . . . . . . . . . . 2
theor`eme. . . . . . . . . . . . . . . . . . . . . . 142
vecteur . . . . . . . . . . . . . . . . . . . . . . . . . . 2
partie rationnelle . . . . . . . . . . . . . . . . . 21
pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
depiler . . . . . . . . . . . . . . . . . . . . . . . . 144
empiler . . . . . . . . . . . . . . . . . . . . . . . 144
pompe (lemme) . . . . . . . . . . . . . . 58, 140
pompe (lemme, version forte) . . . . . 59
prexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
langage . . . . . . . . . . . . . . . . . . . . . . . 151
propre. . . . . . . . . . . . . . . . . . . . . . . . . . . 2
prexiel (langage) . . . . . . . . . . . . . . . . 14
preperiode . . . . . . . . . . . . . . . . . . . . . . . . 20
primitif . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
production . . . . . . . . . . . . . . . . . . . . . . 116
R
r`egle de derivation. . . . . . . . . . . . . . . 116
Rabin M. O. . . . . . . . . . . . . . . . . . . . . . . 33
racine primitive. . . . . . . . . . . . . . . . . . . 24
rationel
cl oture . . . . . . . . . . . . . . . . . . . . . . . . . 22
rationnel
langage . . . . . . . . . . . . . . . . . . . . . . . . 21
operation. . . . . . . . . . . . . . . . . . . . . . . 21
rationnelle (fonction) . . . . . . . . . . . . . 85
relation de transition . . . . . . . . . . . . . 29
S
serie generatrice . . . . . . . . . . . . . . . . . . 96
Sch utzenberger (theor`eme de)108, 154
Scott D. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
semi-groupe . . . . . . . . . . . . . . . . . . . . . 105
aperiodique . . . . . . . . . . . . . . . . . . . 108
indice . . . . . . . . . . . . . . . . . . . . . . . . . 107
neutre . . . . . . . . . . . . . . . . . . . . . . . . 105
periode . . . . . . . . . . . . . . . . . . . . . . . 107
zero. . . . . . . . . . . . . . . . . . . . . . . . . . . 106
semi-lineaire. . . . . . . . . . . . . . . . . . . . . 142
shue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
subset construction . . . . . . . . . . . . . . . 34
suxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
propre. . . . . . . . . . . . . . . . . . . . . . . . . . . 2
168 Index
suxiel (langage) . . . . . . . . . . . . . . . . . 14
symbole . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
initial . . . . . . . . . . . . . . . . . . . . . . . . . 116
inutile. . . . . . . . . . . . . . . . . . . . . . . . .135
non terminal . . . . . . . . . . . . . . . . . . 116
terminal . . . . . . . . . . . . . . . . . . . . . . 116
utile . . . . . . . . . . . . . . . . . . . . . . . . . . 135
syntaxique
conguence . . . . . . . . . . . . . . . . . . . . . . 99
monode . . . . . . . . . . . . . . . . . . . . . . 101
T
theor`eme
Bar-Hillel . . . . . . . . . . . . . . . . . . . . . 140
Chomsky-Sch utzenberger . . . . . . 154
Kleene . . . . . . . . . . . . . . . . . . . . . . . . . 57
Myhill-Nerode. . . . . . . . . . . . . . . . . . 71
Parikh . . . . . . . . . . . . . . . . . . . . . . . . 142
Sch utzenberger . . . . . . . . . . . . . . . . 108
transducteur. . . . . . . . . . . . . . . . . . . . . . 85
transition
fonction . . . . . . . . . . . . . . . . . . . . . . . . 27
relation . . . . . . . . . . . . . . . . . . . . . . . . 29
U
ultimement periodique . . . . . . . . . . . . 20
V
variable . . . . . . . . . . . . . . . . . . . . . . . . . 116
accessible . . . . . . . . . . . . . . . . . . . . . 136
ea cable . . . . . . . . . . . . . . . . . . . . . . 131
inaccessible . . . . . . . . . . . . . . . . . . . 136
vecteur de Parikh. . . . . . . . . . . . . . . . . . 2