TD Automates, langages et applications
Exercices Corrigés TD 7
1
Automates, Langages et Applications - TD 7
1 Automates à pile
Exercice 1 Donner l’automate à pile permettant de reconnaˆıtre le langage suivant :
{anbm | n,m ≥ 0 et n ≤ m}
Corrigé : L’idée est de mettre un symbole sur la pile pour chaque a et de l’enlever pour chaque b.
Comme on veut plus de b que de a, il suffit de rester sur la pile ’$’ tant qu’il y a des b. Notons que
l’automate obtenu n’est pas déterministe.
symbole
pile
A
$
état
a
b
(cid:15)
q1
q2
q1
q2
(q1, AA)
(q1, A$)
(q2, (cid:15))
(q2, (cid:15))
(q2, $)
(q2, $)
(q1,(cid:15))
(q2,(cid:15))
Exercice 2 Donner l’automate à pile permettant de reconnaitre le langage suivant :
{anbmc2(n+m) | n,m ≥ 0}
Corrigé : Comme on veut deux fois plus de c, on met deux symboles sur la pile pour chaque a et
chaque b et on en enleve un a chaque c rencontré. On a besoin de trois états car, quand on commence
à lire les b, on ne peut plus lire de a.
symbole
pile
A
$
état
a
b
Publicité
c
(cid:15)
(q1, AAA)
(q2, AAA)
(q2, AAA)
(q1, AA$)
(q2, AA$)
(q3, (cid:15))
(q3, (cid:15))
(q3, (cid:15))
q1
q2
q3
q1
q2
q3
(q1,(cid:15))
(q3,(cid:15))
Exercice 3 Donner l’automate à pile permettant de reconnaitre le langage suivant :
{anbm | n,m ≥ 0 et n ≤ m ≤ 2n}
Corrigé : Pas d’automate déterministe car on ne sais pas combien de b on va lire. On met donc un
ou deux symboles sur la pile pour chaque a, et on en enlève un pour chaque b lu. On devra donc lire
au minimum autant de b que de a pour se retrouver avec une pile ’$’ (c’est le chemin pris lorsqu’on
met un symbole pour chaque a) et au maximum deux fois plus (c’est le chemin pris lorsqu’on met
deux symboles pour chaque a) ; les autres chemins donnent un nombre intermédiaire de b.
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
2
Exercices Corrigés TD 7
TD Automates, langages et applications
symbole
pile
A
$
état
a
b
(cid:15)
(q1, AA) ; (q1, AAA)
(q1, A$) ; (q1, AA$)
(q2, (cid:15))
Publicité
(q2, (cid:15))
q1
q2
q1
q2
(q1,(cid:15))
(q2,(cid:15))
Exercice 4 Donner l’automate à pile qui permet de reconnaitre le langage des palindromes de longueur
paire (non nulle) sur l’alphabet {a, b}. L’automate obtenu est-il déterministe? Justifiez votre réponse.
Si ce n’est pas le cas, pourriez-vous proposer un automate déterministe qui reconnaisse ce langage ?
Comment modifier l’automate obtenu pour reconnaˆıtre tous les palindromes (pairs et impairs)?
Corrigé : Lorsqu’on rencontre un a, on met un symbole sur la pile (si on est dans la première moitié,
état q1) ou on l’enleve (si on est dans la deuxieme moitié, état q2) ; idem pour les b avec un autre
symbole. Lorsque l’on (cid:40)(cid:40) devine (cid:41)(cid:41) le milieu du mot, on passe avec sans rien consommer et sans modifier
la pile de q1 à q2.
symbole
pile
A
B
$
état
a
b
(cid:15)
q1
q2
q1
q2
q1
q2
(q1, AA)
(q2, (cid:15))
(q1, AB)
(q1, A$)
(q1, BA)
(q2, A)
(q1, BB)
(q2, (cid:15))
(q1, B$)
(q2, B)
(q2,(cid:15))
Il n’est pas déterministe et il n’y a aucun moyen d’en construire un car lors de l’analyse d’un mot, on
Publicité
ne peut pas savoir si la partie (cid:40)(cid:40) retournée (cid:41)(cid:41) a déjà commencée.
Pour reconnaˆıtre tous les palindromes, il faut rajouter la reconnaissance non-déterministe du ca-
ractère du milieu (si le palindrome est de longueur impaire, ce sera un a ou un b; si le palindrome est
de longueur paire, on utilise une transition (cid:15) comme dans le cas précédent). Pour ce caractere-la, on
ne change pas la pile.
symbole
pile
état
a
b
(cid:15)
A
B
$
q1
q2
q1
q2
q1
q2
(q1, AA)
(q2, A)
(q2, (cid:15))
(q1, AB)
(q2, B)
(q1, A$)
(q1, BA)
(q2, A)
(q1, BB)
(q2, B)
(q2, (cid:15))
(q1, B$)
(q2, A)
(q2, B)
(q2,(cid:15))
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard