TD Automates, langages et applications
Exercices Corrig´es TD 7
1
Automates, Langages et Applications - TD 7
1 Automates `a pile
Exercice 1 Donner l’automate `a pile permettant de reconnaˆıtre le langage suivant :
{anbm | n,m ≥ 0 et n ≤ m}
Corrig´e : L’id´ee 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´eterministe.
symbole
pile
A
$
´etat
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 `a pile permettant de reconnaitre le langage suivant :
{anbmc2(n+m) | n,m ≥ 0}
Corrig´e : Comme on veut deux fois plus de c, on met deux symboles sur la pile pour chaque a et
Publicité
chaque b et on en enleve un a chaque c rencontr´e. On a besoin de trois ´etats car, quand on commence
`a lire les b, on ne peut plus lire de a.
symbole
pile
A
$
´etat
a
b
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 `a pile permettant de reconnaitre le langage suivant :
{anbm | n,m ≥ 0 et n ≤ m ≤ 2n}
Corrig´e : Pas d’automate d´eterministe 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`eve 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
Publicité
deux symboles pour chaque a) ; les autres chemins donnent un nombre interm´ediaire de b.
Universit´e Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
2
Exercices Corrig´es TD 7
TD Automates, langages et applications
symbole
pile
A
$
´etat
a
b
(cid:15)
(q1, AA) ; (q1, AAA)
(q1, A$) ; (q1, AA$)
(q2, (cid:15))
(q2, (cid:15))
q1
q2
q1
q2
(q1,(cid:15))
(q2,(cid:15))
Exercice 4 Donner l’automate `a 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´eterministe? Justifiez votre r´eponse.
Si ce n’est pas le cas, pourriez-vous proposer un automate d´eterministe qui reconnaisse ce langage ?
Comment modifier l’automate obtenu pour reconnaˆıtre tous les palindromes (pairs et impairs)?
Corrig´e : Lorsqu’on rencontre un a, on met un symbole sur la pile (si on est dans la premi`ere moiti´e,
´etat q1) ou on l’enleve (si on est dans la deuxieme moiti´e, ´etat 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 `a q2.
Publicité
symbole
pile
A
B
$
´etat
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´eterministe et il n’y a aucun moyen d’en construire un car lors de l’analyse d’un mot, on
ne peut pas savoir si la partie (cid:40)(cid:40) retourn´ee (cid:41)(cid:41) a d´ej`a commenc´ee.
Pour reconnaˆıtre tous les palindromes, il faut rajouter la reconnaissance non-d´eterministe du ca-
ract`ere 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´ec´edent). Pour ce caractere-la, on
ne change pas la pile.
symbole
Publicité
pile
´etat
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´e Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard