M1/2012-2013 Peter Habermehl <[Link]@[Link]-paris-diderot.
fr>
Automates Avancés
Travaux Dirigés no1
x Exercice 1.
Donner un automate (ou une expression regulière) pour les langages suivants :
• Tous les mots sur l’alphabet {a, b} où il n’y a jamais deux a consécutif.
• {x ∈ {0, 1}∗ | x représente un nombre positif codé en binaire divisible par 2}
• {x ∈ {0, 1}∗ | x représente un nombre positif codé en binaire divisible par 3}
• {x ∈ {0, 1}∗ | x représente un nombre positif codé en binaire divisible par 6}
x Exercice 2. De l’automate à l’expression régulière
Donner une expression regulière du langage reconnu par l’automate de la figure 1.
b b b
a
a a
0 1 2 3
b
a, b
Figure 1: automate fini
x Exercice 3. De l’expression regulière à l’automate
• Donner un automate reconnaissant le langage (a + b)∗
• Donner un automate reconnaissant le langage (a∗ b∗ )∗
• Donner un automate reconnaissant le langage a (b + (ba)∗ ) a(a + b)(ba + a)
• Donner un automate reconnaissant le langage ((a + ac)∗ + b∗ )∗ a(b + c)
1
x Exercice 4. Manipulation d’automates
Le produit de shuffle de deux mots u et v est l’ensemble
u ⊔⊔ v = {u0 v0 u1 v1 · · · un vn | n ∈ N et ∀i ∈ {0, 1, . . . , n},
ui ∈ Σ∗ , vi ∈ Σ∗ et u0 u1 · · · un = u, v0 v1 · · · vn = v}.
Le produit de shuffle de deux langages est l’union de tous les produits de shuffle de leurs mots :
[
L ⊔⊔ M = u ⊔⊔ v
u∈L,v∈M
• Donner le produit de shuffle de a∗ b∗ et c∗ d∗ .
• Donner un automate pour a∗ b∗ et un pour c∗ d∗ . Donner un automate pour le produit de
shuffle de a∗ b∗ et c∗ d∗ .
• Soit deux langages L1 et L2 donnés par des automates déterministes. Donner un automate
qui reconnaı̂t L1 ⊔⊔ L2 . On pourra commencer par regarder ce qui se passe si L1 et L2 sont
des singletons.
x Exercice 5. Lemme de pompage (d’itération)
1. Soit un automate fini quelconque A et un mot u reconnu par A. Montrer que si u est
suffisamment long, alors tout chemin réussi de A d’étiquette u passe deux fois par le même
état. Cela reste vraie pour un mot xyz reconnu par A et y suffisamment grand.
2. En déduire le lemme de pompage :
Lemme 1 (de pompage) Soit L un langage régulier. Alors la propriété suivante est vraie:
Il existe un entier N tel que pour tous mots x, y, z avec xyz ∈ L et |y| ≥ N , il existe une
factorisation y = uvw, avec v non vide et pour tout i ≥ 0, xuv i wz ∈ L.
x Exercice 6. Lemme de pompage
1. Montrer que le langage {an bn , n ∈ N} n’est pas régulier.
S
2. Montrer que n≥0 (a+ c)n (b+ c)n + (a + b + c)∗ cc(a + b + c)∗ satisfait la condition du lemme
de pompage. Est-ce que le langage est régulier pour autant ?
x Exercice 7.
Est-ce que le langage {xy | x, y ∈ {a, b}∗ et |x|a = |y|b } est régulier ? Justifier.
x Exercice 8. Transformation de langages
1. Montrer que le carré d’un langage régulier n’est pas nécessairement un langage régulier. Le
carré du langage L étant défini par
L2 = {uu | u ∈ L}.
2. Montrer que la racine carrée d’un langage régulier est un langage régulier. La racine carrée
du langage L étant définie par √
L = {u | uu ∈ L}.
√
On pourra exprimer L comme combinaison régulier de langages obtenus à partir d’un
automate reconnaissant L.