TD langages rationnels et automates

Exercice 1 (Expressions régulières) Décrire aussi simplement que possible les langages définis par les
expressions régulières suivantes sur l’alphabet {𝑎, 𝑏} :
1. 𝑎(𝑎|𝑏)∗
2. 𝑎∗ |𝑏 ∗
3. (𝑏|𝑎𝑏)∗ (𝑎|𝜀)
4. (𝑎𝑎|𝑏)∗
5. (𝑎𝑏 ∗ 𝑎|𝑏)∗
Correction :
1. mots commençant par 𝑎
2. mots n’ayant que des 𝑎 ou que des 𝑏
3. mots n’ayant pas deux 𝑎 consécutifs
4. mots avec des blocs de 𝑎 de longueur paire
5. mots ayant un nombre pair de 𝑎

Exercice 2 (Expressions régulières) Donner des expressions régulières caractérisant les langages suivants
sur l’alphabet {𝑎, 𝑏} :
1. mots de longueur au plus deux
2. mots de longueur paire
3. mots contenant la séquence 𝑎𝑏 mais pas la séquence 𝑏𝑎
4. mots contenant au plus l’une des deux séquences 𝑎𝑏 ou 𝑏𝑎
5. mots contenant la séquence 𝑎𝑏 mais pas la séquence 𝑎𝑎
Correction :
1. (𝜀|𝑎|𝑏)(𝜀|𝑎|𝑏)
2. ((𝑎|𝑏)(𝑎|𝑏))∗
3. 𝑎∗ 𝑎𝑏𝑏 ∗
4. 𝑎∗ 𝑏 ∗ |𝑏 ∗ 𝑎∗
5. 𝑏 ∗ 𝑎𝑏(𝑎𝑏|𝑏)∗

Exercice 3 (Automates) Donner de automates reconnaissant les langages suivants :

Exercice 4 (Déterminisation) On considère l’automate suivant sur l’alphabet {𝑎, 𝑏}.

1 𝑎 2
𝑎
𝑎 𝑎
𝑏
4 3
1. Déterminiser l’automate. 𝑏
2. Donner une expression régulière décrivant le langage reconnu par l’automate.
Correction :
1. À gauche, l’automate déterminisé, à droite la correspondance entre les états de l’automate déterminisé et
des ensembles d’états de l’automate de départ.

𝐶
𝑏 𝑎
𝐴 {1}
𝐴 𝑎 𝐵 𝐵 {2, 3, 4}
𝑎 𝐶 {3}
𝑏 𝐷 {1, 3}
𝑏
𝐷

1
 2. L’automate reconnaît n’importe quelle répétition des motifs 𝑎𝑏, 𝑎𝑎𝑏 et 𝑎𝑏𝑏. D’où l’expression (𝑎𝑏|𝑎𝑎𝑏|𝑎𝑏𝑏)∗ .

Exercice 5 (Langages non reconnaissables) On veut montrer que le langage 𝑃 formé par l’ensemble
des palindromes sur l’alphabet { 0, 1 } ne peut pas être décrit par une expression régulière. Pour ceci, on
commence le raisonnement suivant : « Supposons que 𝑃 peut être décrit par une expression régulière. Alors
il est également reconnaissable par un automate fini 𝐴. Notons 𝑁 le nombre d’états de 𝐴, et considèrons le
mot 𝑚 = 0𝑁 +1 10𝑁 +1 . Le mot 𝑚 étant un palindrome, il doit donc être reconnu : il existe dans 𝐴 un chemin
acceptant étiqueté par 𝑚. »
1. Montrer que les 𝑁 premières transitions du chemin acceptant 𝑚 comportent au moins un cycle.
2. En déduire l’existence d’un mot qui est accepté par 𝐴 alors qu’il n’est pas un palindrome.
3. Compléter la preuve du fait que 𝑃 n’est pas reconnaissable.
4. Avec la même technique, démontrer que le langage 𝐵 formé des mots dont la longueur est une
puissance de 2, n’est pas non plus reconnaissable (ou en utilisant directement le lemme de l’étoile).
Correction :
1. Ces 𝑁 premières transitions visitent 𝑁 + 1 états. Comme il n’y a que 𝑁 états différents dans l’automate,
au moins un état est visité deux fois. La portion de chemin comprise entre les deux premières visites de
cet état forme un cycle de longueur 𝑘 ≥ 1.
2. On obtient encore un chemin acceptant en retirant un passage dans le cycle identifié ci-dessus. Ce chemin
raccourci est étiqueté par le mot 0𝑁 +1−𝑘 10𝑁 +1 , qui est alors reconnu sans être un palindrome.
3. Structure complète : preuve par l’absurde. On suppose que 𝑃 est reconnaissable, et par les deux points
suivants on en déduit une contradiction (la déclaration que 0𝑁 +1−𝑘 10𝑁 +1 appartient à 𝑃). Donc 𝑃 ne
pouvait pas être reconnaissable.
4. Note : pour cet autre langage, il n’y a pas besoin de choisir une zone particulière du mot où chercher une
boucle (i.e. la version faible du lemme de l’étoile suffit).

Exercice 6 (Construction directe d’un automate déterministe pour une expression régulière) Remarquons
que chaque lettre d’un mot 𝑚 reconnu par une expression régulière 𝑒 peut être mise en relation avec une
des lettres de 𝑒. Ainsi par exemple, le mot 𝑎𝑎𝑏𝑎𝑎𝑏 est reconnu par (𝑎|𝑏)∗ 𝑎(𝑎|𝑏) de la façon suivante :

𝑎 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)
𝑎 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)
𝑏 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)
𝑎 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)
𝑎 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)
𝑏 (𝑎|𝑏)∗ 𝑎(𝑎|𝑏)

Nous allons distinguer les différentes lettres d’une expression pour faciliter ce suivi. Notre expression
régulière devient donc

(𝑎1 |𝑏2 )∗ 𝑎3 (𝑎4 |𝑏5 )

On veut alors construire un automate dont les états sont des ensembles de lettres (par exemple : {𝑎1 , 𝑏2 , 𝑎3 }).
L’état 𝑞 va reconnaitre les mots dont la première lettre appartient à 𝑞 (donc dans notre exemple, un 𝑎
correspondant à 𝑎1 ou 𝑎3 , ou un 𝑏 correspondant à 𝑏2 ).
Rappelons que l’on dispose déjà d’une fonction null(𝑒) qui renvoie vrai si l’expression 𝑒 reconnaît le
mode vide 𝜀.

null(∅) = false
null(𝜀) = true
null(𝑎) = false
null(𝑒1 𝑒2 ) = null(𝑒1 ) ∧ null(𝑒2 )
null(𝑒1 | 𝑒2 ) = null(𝑒1 ) ∨ null(𝑒2 )
null(𝑒 ∗ ) = true

2
 1. Définir deux fonctions first et last renvoyant respectivement l’ensemble des premières lettres et des
dernières lettres possibles d’un mot reconnu par une expression régulière. On doit donc avoir
first((𝑎1 |𝑏2 )∗ 𝑎3 (𝑎4 |𝑏5 )) = {𝑎1 , 𝑏2 , 𝑎3 }
last((𝑎1 |𝑏2 )∗ 𝑎3 (𝑎4 |𝑏5 )) = {𝑎4 , 𝑏5 }
2. Définir une fonction follow qui prend en entrée une lettre 𝑎 et une expression 𝑒, et qui renvoie
l’ensemble des lettres qui peuvent suivrent 𝑎 dans un mot reconnu par 𝑒. On doit donc avoir
follow(𝑎1 , (𝑎1 |𝑏2 )∗ 𝑎3 (𝑎4 |𝑏5 )) = {𝑎1 , 𝑏2 , 𝑎3 }
3. On propose alors de construire un automate déterministe pour une expression régulière 𝑒 en se basant
sur les fonctions précédentes, appliquées à l’expression 𝑒# obtenu en ajoutant une lettre spéciale à la
fin de 𝑒.
Préciser ce que seront l’état initial, les états acceptants, et les transitions. Appliquer cette construction
à notre exemple (𝑎1 |𝑏2 )∗ 𝑎3 (𝑎4 |𝑏5 )#.
Indication. L’état initial doit être {𝑎1 , 𝑏2 , 𝑎3 }, et il en part les deux transitions
({𝑎1 , 𝑏2 , 𝑎3 }, 𝑎, {𝑎1 , 𝑏2 , 𝑎3 , 𝑎4 , 𝑏5 }) et ({𝑎1 , 𝑏2 , 𝑎3 }, 𝑏, {𝑎1 , 𝑏2 , 𝑎3 }).
Remarque : et ça se code en caml.
Correction :
1.
first(∅) = ∅
first(𝜀) = ∅
first(𝑎) = {𝑎}
first(𝑒1 𝑒2 ) = first(𝑒1 ) ∪ first(𝑒2 ) si null(𝑒1 )
first(𝑒1 𝑒2 ) = first(𝑒1 ) sinon
first(𝑒1 | 𝑒2 ) = first(𝑒1 ) ∪ first(𝑒2 )
first(𝑒 ∗ ) = first(𝑒)
last(∅) = ∅
last(𝜀) = ∅
last(𝑎) = {𝑎}
last(𝑒1 𝑒2 ) = last(𝑒1 ) ∪ last(𝑒2 ) si null(𝑒2 )
last(𝑒1 𝑒2 ) = last(𝑒2 ) sinon
last(𝑒1 | 𝑒2 ) = last(𝑒1 ) ∪ last(𝑒2 )
last(𝑒 ∗ ) = last(𝑒)
2.
follow(𝑐, ∅) = ∅
follow(𝑐, 𝜀) = ∅
follow(𝑐, 𝑎) = ∅
follow(𝑐, 𝑒1 𝑒2 ) = follow(𝑐, 𝑒1 ) ∪ follow(𝑐, 𝑒2 ) ∪ first(𝑒2 ) si 𝑐 ∈ last(𝑒1 )
follow(𝑐, 𝑒1 𝑒2 ) = follow(𝑐, 𝑒1 ) ∪ follow(𝑐, 𝑒2 ) sinon
follow(𝑐, 𝑒1 | 𝑒2 ) = follow(𝑐, 𝑒1 ) ∪ follow(𝑐, 𝑒2 )
follow(𝑐, 𝑒 ∗ ) = follow(𝑐, 𝑒) ∪ first(𝑒) si 𝑐 ∈ last(𝑒)
follow(𝑐, 𝑒 ∗ ) = follow(𝑐, 𝑒) sinon
3. — État initial : first(𝑒#)
— Transitions : 𝑠.𝑐 = ⋃𝑐𝑖 ∈𝑠 follow(𝑐𝑖 , 𝑒#)
— États acceptants : états contenant #
Sur l’exemple :
num état 𝑎 𝑏
1 {𝑎1 , 𝑏2 , 𝑎3 } 1 2 1
2 {𝑎1 , 𝑏2 , 𝑎3 , 𝑎4 , 𝑏5 } 2 3 4
3 {𝑎1 , 𝑏2 , 𝑎3 , 𝑎4 , 𝑏5 , #} 3 3 4
4 {𝑎1 , 𝑏2 , 𝑎3 , #} 4 2 1