Théorie des Langages - TD 7
AUTOMATES À PILE
Exercice 1 - Donnez deux automates à pile (acceptation par pile vide ; par état final) qui reconnaissent chacun
des langages suivants :
1. L1 = {an bm |n, m ≥ 0 et n ≤ m} 3. L3 = {an bm |n, m ≥ 0 et n ≤ m ≤ 2n}
2. L2 = {an bm c2(n+m) |n, m ≥ 0} 4. L4 = {w ∈ (a + b)∗ ||w|a = |w|b }
Exercice 2 - Soient L1 = {ab2p+1 c|p ≥ 0} et L2 = {an bm cm d n |m, n ≥ 0}
1. L1 est-il régulier ? Construire l’automate qui reconnaît L1
2. L2 est-il hors-contexte ? Construire l’automate qui reconnaît L2
Exercice 3 - Soit l’automate à pile suivant reconnaissant le langage L par état final :
a, A/AA b, A/ε
a, Z0 /AZ0 b, A/ε
0 1 2
ε, A/ε ε, A/ε
1. Cet automate est-il déterministe ?
2. Donner les différentes étapes de reconnaissance du mot aaab
3. Quel langage est généré par cet automate ?
4. Modifier l’automate de façon à avoir une reconnaissance par pile vide
Exercice 4 - Soit l’automate à pile suivant reconnaissant le langage L par état final :
a, T /T T c, ε/ε b, T /ε
ε, T /T b, T /ε ε, Z0 /Z0
0 1 2 3
a, Z0 /T Z0
1. Cet automate est-il déterministe ?
2. Donner les différentes étapes de reconnaissance des mot aacbb et ab
3. Quel langage est généré par cet automate ?
4. Modifier l’automate de façon à avoir une reconnaissance par pile vide
Exercice 5 - Donnez l’automate à pile correspondant à chacune des grammaires sous forme normale de Greibach
suivantes :
G1 = hV1 , Σ1 , P1 , S1 i G2 = hV2 , Σ2 , P2 , S2 i G3 = hV3 , Σ3 , P3 , S3 i
V1 = {a, b, S1 , B,C} V2 = {a, b, c, S2 , D, E} V3 = {a, b, c, d, S3 , F, G, H}
Σ1 = {a, b} Σ2 = {a, b, c} Σ3 = {a, b, c, d}
S1 → a|aS1 |aBC S2 → cD S3 → c|dFS3 |aGH
B → aB|bC D → aS2 |bE F → bGH|cF
C→b E → aD|cS2 |b G → bH|c
H → aG|d
Exercice 6 - Soient les deux automates à pile suivants. Donnez les grammaires algébriques correspondantes.
a, Z0 /A
a, A/AA b, A/ε a, A/AA c, B/ε
b, A/ε c, B/ε
0 1 0 1
a, Z0 /A b, B/BB d, A/ε
b, A/BA
Exercice 7 - Trouvez une grammaire algébrique pour chacun des langages suivants :
1. L1 = {ak b j cl |k ≤ j ou j ≤ l}
2. L2 = {w||w|a = |w|b ou |w|a = |w|c }
3. L3 = {w1 .w2 ||w1 |a = |w1 |b et |w2 |b = |w2 |c }
4. L4 = {an bm |n > 0, m = n ou m = 2n}
5. L5 = {an br as bt |n = s ou r = t}
