TD2 Licence INF208 Théorie des langages, 2006/07
Exo 1 (Glushkov)
Un langage L ⊆ Σ∗ est dit local s’il existe des ensembles de symboles P, S ⊆ Σ ainsi qu’un
ensemble de mots de 2 lettres T ⊆ Σ2 tels que L \ {} = (P Σ∗ ∩ Σ∗ S) \ Σ∗ T Σ∗ .
1. Montrer que tout langage local est accepté par un NFA ayant n + 1 états, où n = |Σ|.
2. Montrer que le langage (ab)∗ est local.
3. Donner un exemple de langage régulier qui n’est pas local.
4. Montrer que pour tout langage régulier L ⊆ Σ∗ il existe un alphabet Γ, un langage local
K ⊆ Γ∗ et un morphisme alphabétique h : Γ → Σ tels que L = h(K).
5. Soit E une expression rationnelle sur Σ dans laquelle chaque lettre apparaı̂t au plus une fois.
Montrer (en utilisant la construction de Glushkov) que le langage associé L(E) est local.
Exo 2 (algorithme de minimisation de Brzozowski)
Soit A = (Q, Σ, δ, I, F ) un NFA sans transitions-. Le langage à gauche LA g (q) de l’état q ∈ Q
est le langage accepté par l’automate Ag (q) = (Q, Σ, δ, I, q). Le langage à droite LA d (q) de l’état
q ∈ Q est le langage accepté par l’automate Ad (q) = (Q, Σ, δ, q, F ).
Soit d(A) l’automate des parties associé à A (en ne gardant que les états accessibles). Soit r(A)
l’automate miroir associé à A (obtenu en renversant les flèches et en échangeant I et F ).
1. Montrer que r(A) reconnait les miroirs de mots dans L(A) : L(r(A)) = L(A)R .
r(A)
2. Montrer que le langage à gauche Lg (q) de l’état q dans r(A) est le miroir du langage à
droite LA
d (q) de q dans A. (Pareil pour gauche et droite inversés.)
d(A)
3. Montrer que chaque langage à droite Ld (R) associé à un état R de d(A) est l’union des
langages à droite LA
d (r), où r ∈ R.
4. Montrer que A est déterministe ssi les langages à gauche associés à ses états sont deux à deux
disjoints et |I| = 1.
5. Montrer qu’un DFA complet, dont tous les états sont accessibles, est minimal ssi les langages
à droite associés à ses états sont deux à deux différents.
6. Montrer que d(r(d(r(A)))) est l’automate minimal de A.
Exo 3
Donner des formules MSO φL pour chacun des langages réguliers L suivants :
1. L1 = {w ∈ {a, b}∗ | |w|a est divisible par 3}
2. L2 ⊆ {a, b}∗ contient tous les mots w tels que dans chaque préfixe v de w, la différence
|w|a − |w|b est 0, 1 ou 2.
3. L3 ⊆ {a, b}∗ contient tous les mots w qui n’ont pas de facteur aab.
4. L4 ⊆ {a, b}∗ contient tous les mots w qui n’ont pas de sous-mot aab.
5. L5 ⊆ {a, b}∗ contient tous les mots w qui ont un nombre pair de facteurs abba.
1
Exo 4 Montrer que tout langage rationnel sur un alphabet Σ est définissable dans MSOL par
induction structurelle sur une expression rationnelle définissant le langage.
Étant donné une expression rationnelle E, on pourra construire une formule ϕE (x, y) avec 2
variables libres x et y telle qu’un mot w satisfait ϕE (x, y) sous une interprétation {x 7→ i, y 7→ j}
ssi i 6 j et le facteur du mot w compris entre les positions i et j est dans L(E).
Exo 5 On considère la logique FOL(+) dans laquelle les formules sont construites à partir des
formules atomiques a(x), qui s’interprète comme “la position x porte la lettre a”, et x = y + z avec
l’interprétation naturelle de l’addition.
1. Montrer que tout langage définissable dans FOL est aussi définissable dans FOL(+).
2. Montrer que {an bn | n > 0} est définissable dans FOL(+).
3. Déduire que la relation ternaire R(x, y, z) ≡ x = y + z n’est pas définissable dans MSOL.
Exo 6
Soit Σ0 = {a}, Σ1 = {g}, Σ2 = {f }.
1. Construire un automate d’arbre montant (descendant, respectivement) qui reconnait l’en-
semble des arbres de la forme f (f (a, t1 ), g(t2 )), où t1 , t2 ∈ T (Σ), Σ = Σ0 ∪ Σ1 ∪ Σ2 .
2. Construire un DTA (automate déterministe montant) qui reconnaı̂t l’ensemble des arbres de
T (Σ0 ∪ Σ1 ) dont la hauteur est paire.
Exo 7
Soit Σ = Σ0 ∪ Σ1 ∪ Σ2 , où Σ0 = {0, 1}, Σ1 = {not}, Σ2 = {and,or}.
Construire un DTA qui reconnaı̂t les arbres de T (Σ) correspondant aux formules booléennes
qui s’évaluent à Vrai.
Exo 8
On considère des arbres binaires (chaque nœud a 0 ou 2 fils) dont les nœuds sont étiquetés par
Σ = Σ0 ∪ Σ2 , où Σ0 = Σ2 = {a, b}.
Construire des automates d’arbre (montants ou descendants) reconnaissant les langages suivants
(si possible, proposez des automates déterministes) :
1. L’ensemble des arbres dont la feuille la plus à gauche est étiquetée par a.
2. L’ensemble des arbres contenant 2 nœuds u, v étiquetés par a, tels que u est ancêtre de v.
3. L’ensemble des arbres contenant 2 nœuds u, v étiquetés par a, tels que u et v ne sont pas
ancêtre l’un de l’autre.
4. L’ensemble des arbres contenant un nombre pair de nœuds étiquetés par a.
5. L’ensemble des arbres dont la branche la plus à droite contient au moins un nœud étiqueté
par a.
