Théorie des langages : Td 3 les grammaires suite
Télécharger PDFNF11 – TD3 Les grammaires - Suite
Exercice 1Considérons la grammaire : S → aSbS | bSaS | ε Questions : 1. Montrer que cette grammaire est ambiguë en considérant deux dérivations gauches différentes pour la phrase abab. 2. Construire les dérivations droites correspondant à abab. 3. Construire les arbres d’analyse correspondant à abab. 4. Quel est le langage engendré par cette grammaire ?
Exercice 2Considérons la grammaire : R → R | R R → RR R → R* R → ( R ) R → a R → b Questions : 1. Que génère cette grammaire ? 2. Montrer que cette grammaire est ambiguë.
Exercice 3On veut établir une grammaire d’expressions arithmétiques prenant en compte : 1. La priorité des opérateurs x et / sur les opérateurs + et – 2. L’écriture de parenthèses 3. L’utilisation d’identificateur de variable 4. D’une seule forme de nombre Questions : 1. Donner l’ensemble des terminaux de cette grammaire 2. Donner une grammaire qui peut être récursive à gauche (la variable en tête de règle peut se retrouver en première position du corps de la règle) 3. Donner une grammaire non récursive à gauche 4. Donner l’arbre de dérivation correspondant à 25 x ( a + 30 – 12 / 4 )
Exercice 4Une grammaire sous forme normale de Chomsky (FNC) est une grammaire dont toutes les productions sont de la forme : A → BC; A→ a où a est un terminal et A, B et C des non terminaux et telle que seul l’axiome peut générer le mot vide. Questions : 1. Transformer la grammaire suivante pour la mettre sous forme FNC : S → A | Bbb
A → aB | bS | ε
B → ABb | Bb | ε 2. Montrer que toute grammaire de type 2 peut être transformée en une grammaire FNC.