PandaCodeur · Exercices 1 / 2

Exercices de compilation : 1. Langages et automates

Six exercices progressifs avec indices et solutions détaillées.

Mode d’emploi

Objectif : passer des définitions à une construction vérifiable. Prévoyez 60 à 90 minutes. Pour chaque exercice, notez un mot accepté et un mot refusé avant de consulter la solution.

1. Produits de langages : découverte

L={ε,a}, K={b,bb}. Calculer LK, KL et L². Indice : énumérer puis supprimer les doublons.

Afficher la correction expliquée

LK={b,bb,ab,abb} ; KL={b,bb,ba,bba} ; L²={ε,a,aa}. En général LK ≠ KL, même si la concaténation est associative.

2. Écrire un motif : application

Décrire les mots binaires contenant exactement deux 1. Indice : les 0 peuvent se placer avant, entre et après les deux 1.

Afficher la correction expliquée

0*10*10*

11, 0101 et 10010 sont acceptés ; ε, 1 et 111 sont refusés. Chaque 1 est imposé une fois ; seuls les 0 sont répétés.

3. Construire un AFD : application

Construire un AFD complet sur {a,b} acceptant les mots sans facteur bb. Indice : mémoriser si la dernière lettre est b.

Afficher la correction expliquée

État	a	b	Final
→ q0 : début ou dernier a	q0	q1	Oui
q1 : dernier b	q0	p	Oui
p : bb déjà rencontré	p	p	Non

L’invariant de p est irréversible : un mot contenant déjà bb ne peut plus satisfaire la propriété. ε est accepté en q0 ; baba en q0 ; abb finit au puits.

4. Déterminiser avec ε : consolidation

Initial q0 ; final q1 ; alphabet {0,1}
δ(q0,0)={q0,q1} ; δ(q0,ε)={q1}
δ(q1,1)={q1} ; autres transitions ∅

Donner un AFD complet. Indice : calculer d’abord ε-fermeture({q0}).

Afficher la correction expliquée

Ensemble	0	1	Final
→ A={q0,q1}	A	B	Oui
B={q1}	P	B	Oui
P=∅	P	P	Non

Le langage est 0*1*. ε est accepté grâce au chemin ε de q0 à q1. Toute lecture de 0 après un 1 conduit au puits.

5. Minimiser : consolidation

Initial A ; finaux C,D
       a   b
A      B   C
B      A   D
C      D   C
D      C   D

Minimiser. Indice : comparer les blocs de destination plutôt que les noms des états.

Afficher la correction expliquée

P0={{A,B},{C,D}} est déjà stable : sur a, chaque bloc reste dans lui-même ; sur b, A et B vont au bloc final, C et D y restent. Tous les états sont accessibles : A par ε, B par a, C par b, D par ab. Le quotient possède deux états : X={A,B} non final et Y={C,D} final ; δ(X,a)=X, δ(X,b)=Y, δ(Y,a)=Y, δ(Y,b)=Y. Il reconnaît les mots contenant au moins un b.

6. Preuve de clôture : approfondissement

Construire un automate pour l’intersection de « nombre pair de a » et « nombre impair de b ». Indice : produit cartésien.

Afficher la correction expliquée

État (parité a, parité b)	a	b	Final ?
q00	q10	q01	Non
q10	q00	q11	Non
q01	q11	q00	Oui
q11	q01	q10	Non

Chaque composante mémorise une parité. Le produit part de (pair,pair) et seul (pair,impair) est final. Une induction sur la longueur du mot prouve que l’état après w représente exactement les deux parités de w.