Automates et langages
Corrigé de l’examen — RICM1— 8 janvier 2003
Exercice 1 : Un automate et son langage
1. Voici les productions de grammaire obtenues directement à partir de l’automate:
P → aP P → aQ
Q → bP Q → R
R → bR R → cQ R → bP R →
Les non-terminaux de la grammaire sont {P,Q,R}, le symbole initial est P .
2. En dénotant avec Xp , Xq , Xr les langages acceptés à partir des états p, q et r respectivement,
le système d’équations pour ces langages est:
Xp = aXp + aXq
Xq = bXp + Xr
Xr = bXr + cXq + bXp +
En remplaçant Xq dans les équations 1 et 3 on obtient:
Xp = aXp + abXp + aXr
Xr = bXr + cbXp + cXr + bXp +
La deuxième équation implique:
Xr = (b + c)∗ (cbXp + bXp + )
d’où, en remplaçant dans la première équation:
Xp = (a + ab)Xp + a(b + c)∗ (cb + b)Xp + a(b + c)∗
Finalement, on obtient l’expression régulière équivalente à l’automate :
∗
Xp = (a + ab + a(b + c)∗ (cb + b)) a(b + c)∗
3. Le tableau de successeurs obtenu par déterminisation est :
A B C D
{p} {p,q,r} {p,r} {q,r}
a {p,q,r} {p,q,r} {p,q,r} ∅
b ∅ {p,r} {p,r} {p,r}
c ∅ {q,r} {q,r} {q,r}
L’automate est donc : a b
b
a
A B C
a
b
b,c c
c
∅ a D
a,b,c
c
Exercice 2: Un langage régulier plus intéressant
1. Le langage contient les mots de longueur multiple de 3 et impaire, formés avec le symbole a.
2. Soit K = (aaa)∗ et L = (aa)∗ . L’automate acceptant K est :
2
a a
1 a 3
L’automate acceptant L est :
a
p q
a
L’automate acceptant L est :
a
p q
a
L’automate acceptant M = K − L = K ∩ L est:
a a
1,p 2,q 3,p
a a
3,q a 2,p a 1,q
3. M n’est pas vide, car l’automate contient un chemin 1p → 2q → 3p → 1q de l’état initial à
l’état final.
M contient une infinité de mots, car l’automate contient un cycle σ = 1p → 2q → 3p →
1q → 2p → 3q → 1p accessible de l’état initial, tel que l’état final est accessible à partir de
σ, étiqueté par un mot non vide a6 .
4. a3 (a6 )∗
5. 3 + 6k | k ∈ N
Exercice 3: Un langage non-régulier
1. La grammaire qui engendre {ai bj | i < j} peut être donnée avec les productions suivantes :
I → aIb | Ib | b
La grammaire qui engendre {ai bj | i > j} peut être donnée avec les productions suivantes :
J → aJb | aJ | a
La grammaire qui engendre T est donnée par les productions antérieures, plus les productions
suivantes :
S→I | J
Les non-terminaux de la grammaire sont {S,I,J}. Le symbole initial est S.
2. Voici un automate à pile pour T , en supposant que l’automate commence avec une pile
contenant le symbole Z (l’état A sert a accepter les mots qui ont plus de a, l’état B ceux
avec plus de b.)
a,push(a) b,pop(a)
,pop(a)
A
b,pop(Z)
B b
3. a∗ b∗ = {an bm | n,m ∈ N}
a∗ b∗ − T = {an bm | n,m ∈ N ∧ ¬(n 6= m)} = {ai bi | i ∈ N}
4. Supposons que T est régulier. Alors, par les propriétés de fermeture des langages réguliers,
T est aussi régulier. Comme a∗ b∗ est régulier, il en résulte que a∗ b∗ ∩ T = a∗ b∗ − T est aussi
régulier.
Mais a∗ b∗ − T = {ai bi | i ∈ N} n’est pas régulier (vu en cours).
Par conséquent, on a une contradiction de l’hypothèse de régularité de T .
Exercice 4: Une intersection
1. On a vu ces langages en TD.
P = {an bm am bn | n,m ∈ N}
Q = ((a + b)3 )∗ = {w | w ∈ {a,b}∗ et |w| est multiple de 3}
2. Nous allons utiliser comme non-terminaux pour l’intersection S0 ,S1 ,S2 ,R0 ,R1 ,R2 . La signifi-
cation du symbole Si (resp. Ri ) est la même que celle de S (resp. R), et encore que le nombre
de terminaux (c-à-d a et b) déjà générés est i(mod 3).
Chaque transition de la grammaire de départ donne plusieurs transitions de la nouvelle
grammaire, ainsi pour S → aSb on obtient trois règles: S0 → aS2 b; S1 → aS0 b; S2 → aS1 b
(si avant la production on avait i(mod 3) terminaux, alors après on a 2 terminaux de plus,
c-à-d i + 2(mod 3)).
On peut terminer la dérivation si est seulement si notre symbole est R, et le nombre de
terminaux est multiple de 3, ce qui correspond à R0 dans la nouvelle grammaire. Pour cette
raison la seule production qui donne est R0 → .
Finalement on obtient la grammaire suivante:
S0 → a S2 b | R0
S1 → a S0 b | R1
S2 → a S1 b | R2
R0 → b R2 a |
R1 → b R0 a
R2 → b R1 a
avec S0 comme symbole initial.
