Page 1 sur 2
Théorie des langages et automates
Série de TD n°4
Exercice 1
On a la grammaire suivante (en forme de Backus-Naur (BNF) souvent utilisée pour définir la
syntaxe des langages de programmation)
<polynome>::= <monome> | <polynome> + <monome>
<monome>:: = <atome> | <monome> * <atome>
<atome> ::= <variable> | <nombre> | <variable> ^ <nombre>
<nombre>::= 2 | 3 | 4 | 7
<variable>::=x | y | z
1. Représenter cette grammaire comme (V,,S, R)
2. Est-ce qu'elle engendre les polynômes 3*x^2+x*y*z^3+7 et 5*x*y+4 ? Si oui, dessiner
les arbres de dérivation
Exercice 2
Considérons la grammaire G suivante :
Grammaire G=({S,X},{0,1},R,S) où R={S → 0X, X → |S1 }
1. La grammaire G est-elle régulière ? Pourquoi ?
2. Quel est le langage L(G) engendré par cette grammaire ?le montrer.
3. Ce langage est-il régulier ?
Exercice 3
Soit la grammaire G:
S → SS
S → a2
Montrer que G est ambiguë.
Exercice 4
Soit G la grammaire définie par G=({S},{a,b},R,S) où R={S → | a | b | aSa | bSb }.
Montrer que G génère les palindromes sur {a,b}*.
Exemples de palindromes: aabbaa, aba, bbb
Exercice 5
Construire un automate à pile acceptant le langage suivant:
L={ambncn | n,m0}
Page 2 sur 2
Exercice 6
Construire un automate à pile acceptant le langage suivant:
L={w {a,b}*| |w|a = |w|b}
Exercice 7
1. Construire un automate à pile acceptant le langage suivant:
L={ ycym | y {a,b}*}(ym: chaîne miroir de y)
2. Donner une grammaire générant le langage L et construire à partir de cette grammaire un
automate à pile acceptant L.
Donner les différentes configurations de l'automate à pile pour la reconnaissance de la chaîne
abbcbba.
Exercice 8
Soit G la grammaire dont l’alphabet est {a,b} et dont les productions sont
S → AA
A → aAa | bBb | aa | bb
Pour chaque mot w de {a,b}*, on note wR le mot obtenu à partir de w en inversant l’ordre des
symboles (image miroir de w).
1. Montrer (par induction) que le language engendré par G est l’ensemble des mots de la
forme uuRvvR avec |u| 1 et |v| 0
2. Montrer que G est ambiguë.
3. Construire un automate à pile reconnaissant L(G).
Exercice 9
A partir de la grammaire G définie par les productions S → + S S | x | y, construire un
automate à pile reconnaissant L(G).
Analyser la chaîne + x + + x x y à l'aide de cet automate en précisant à chaque étape l'état de
l'automate, la chaîne restant à analyser et le contenu de la pile.