Théorie des langages : Td 3 grammaire
Télécharger PDFL3 - Langages et Compilation1
TD 3 - Grammaire
Qu 1.Soit la grammaire( {a, b, c},{S}, S,{S→Saab|Sbb|c|ε}) .
a.Donner tous les mots de longueur six engendr ́es par la grammaire. Pour chacun de ces
mots, proposer un arbre de d ́erivation.
b.Quel est le langage engendr ́e par cette grammaire ?
Qu 2.Soit la grammaire G =( {a, b, c},{S, U}, S, P}) o`u l’ensemble de r`eglesPest :{ S→S c|U
U→a U b|ε
a.Donner quatre mots engendr ́es par la grammaire. Pour chacun de ces mots, proposer un
arbre d’analyse.
b.Caract ́eriser l’ensemble des mots qui d ́erivent de la variableU.
c.Quel est le langage engendr ́e par G ?
Qu 3.Donner une grammaire qui engendre le langage{an bm cn+m :n, m∈N}.
Qu 4.Soit la grammaire( {a, b},{S}, S,{S→SS|aSb|bSa|ε}) .
a.Donner tous les mots engendr ́es par la grammaire de longueurs 0, 1, 2, 3 et 4.
b.Quel est le langage engendr ́e par cette grammaire. Justifier.
Qu 5.On d ́efinit l’ensemble des mots bien parenth ́es ́es admettant les deux types de par-
enth`eses ( ) et [ ] comme le plus petit ensemble tel que :
•εest bien parenth ́es ́e;
•sixest bien parenth ́es ́e alors (x) et [x] sont bien parenth ́es ́es;
•sixetysont bien parenth ́es ́es alorsxyest bien parenth ́es ́e.
Donner une grammaire qui engendre cet ensemble.
Qu 6.On veut engendrer les expressions arithm ́etiques construites `a partir de la multiplication.
L’alphabet des lettres terminales est Σ ={∗,(,), id, cte}o`uidd ́ecrit les variables etcteles
constantes num ́eriques.
a.Donner un exemple qui montre que la grammaire( Σ,{E}, E,{E→E∗E|(E)|id|cte}) est ambigu ̈e.
b.En donner une version non ambigu ̈e (et de pr ́ef ́erence qui force l’associativit ́e `a gauche de
la multiplication).
V ́erifier que le mot donn ́e pr ́ec ́edement en exemple n’admet qu’un arbre d’analyse.
Qu 7.On veut engendrer les expressions arithm ́etiques construites `a partir de la soustraction
unaire et de la multiplication.
a.Donner un exemple qui montre que la grammaire( {−,∗,(,), id, cte},{E}, E,{E→−E|
E∗E|(E)|id|cte}) est ambigu ̈e.
b.En donner une version non ambigu ̈e (et de pr ́ef ́erence telle que l’op ́erateur unaire soit
prioritaire sur l’op ́erateur binaire et qui force l’associativit ́e `a gauche de la multiplication).