Théorie des langages : Td 3 grammaire
Télécharger PDFTD 3 - Grammaire
Question 1
Soit la grammaire G = ({a, b, c}, {S}, S, P) où P = {S → Saab | Sbb | c | ε}.
a. Donner tous les mots de longueur six engendrés par la grammaire. Pour chacun de ces mots, proposer un arbre de dérivation.
b. Quel est le langage engendré par cette grammaire ?
Question 2
Soit la grammaire G = ({a, b, c}, {S, U}, S, P) où P = {S → Sc | U, U → aUb | ε}.
a. Donner quatre mots engendrés par la grammaire. Pour chacun de ces mots, proposer un arbre d’analyse.
b. Caractériser l’ensemble des mots qui dérivent de la variable U.
c. Quel est le langage engendré par G ?
Question 3
Donner une grammaire qui engendre le langage {an bm cn+m : n, m ∈ ℕ}.
Question 4
Soit la grammaire G = ({a, b}, {S}, S, {S → SS | aSb | bSa | ε}).
a. Donner tous les mots engendrés par la grammaire de longueurs 0, 1, 2, 3 et 4.
b. Quel est le langage engendré par cette grammaire ? Justifier.
Question 5
On définit l’ensemble des mots bien parenthésés admettant les deux types de parenthèses ( ) et [ ] comme le plus petit ensemble tel que :
• ε est bien parenthésé ;
• si x est bien parenthésé, alors (x) et [x] sont bien parenthésés ;
• si x et y sont bien parenthésés, alors xy est bien parenthésé.
Donner une grammaire qui engendre cet ensemble.
Question 6
On veut engendrer les expressions arithmétiques construites à partir de la multiplication.
L’alphabet des lettres terminales est Σ = {∗, (, ), id, cte}, où id désigne les variables et cte les constantes numériques.
a. Donner un exemple qui montre que la grammaire G = (Σ, {E}, E, {E → E∗E | (E) | id | cte}) est ambiguë.
b. En donner une version non ambiguë (et de préférence qui force l’associativité à gauche de la multiplication).
Vérifier que le mot donné précédemment en exemple n’admet qu’un arbre d’analyse.
Question 7
On veut engendrer les expressions arithmétiques construites à partir de la soustraction unaire et de la multiplication.
a. Donner un exemple qui montre que la grammaire G = ({−, ∗, (, ), id, cte}, {E}, E, {E → −E | E∗E | (E) | id | cte}) est ambiguë.
b. En donner une version non ambiguë (et de préférence telle que l’opérateur unaire soit prioritaire sur l’opérateur binaire et qui force l’associativité à gauche de la multiplication).
FAQ
Q : Qu’est-ce qu’un arbre de dérivation ?
R : Un arbre de dérivation est une représentation graphique des étapes successives qui permettent de générer un mot à partir d’une grammaire. Chaque nœud correspond à une règle appliquée, et les feuilles contiennent les symboles terminaux du mot final.
Q : Comment identifier une grammaire ambiguë ?
R : Une grammaire est ambiguë si un même mot peut être généré par deux arbres de dérivation distincts. Cela signifie qu’il existe plusieurs façons d’appliquer les règles pour obtenir le même résultat.
Q : Que signifie "associativité à gauche" pour un opérateur ?
R : L’associativité à gauche signifie que les opérations sont évaluées de gauche à droite. Par exemple, pour l’expression a∗b∗c, l’associativité à gauche impose de calculer (a∗b)∗c plutôt que a∗(b∗c).