Td 3 les grammaires suite Théorie des langages-téléchar...

Théorie des langages : Td 3 les grammaires suite

Télécharger PDF

Exercice 1

Considérons la grammaire : S → aSbS | bSaS | ε

1. Montrer que cette grammaire est ambiguë en considérant deux dérivations gauches différentes pour la phrase abab

Dérivation gauche 1 : S ⇒ aSbS ⇒ aaSbbS ⇒ aaSbSbS ⇒ aabSbbS ⇒ aabbbS ⇒ aabbbb Dérivation gauche 2 : S ⇒ aSbS ⇒ aSbSbS ⇒ abSbS ⇒ abbbS ⇒ abbbb

2. Construire les dérivations droites correspondant à abab

Dérivation droite 1 : S ⇒ aSbS ⇒ aSbbS ⇒ abbbS ⇒ abbbb Dérivation droite 2 : S ⇒ bSaS ⇒ bSabS ⇒ bbabS ⇒ bbabb

3. Construire les arbres d’analyse correspondant à abab

Arbre 1 : ``` S / \ a S / \ b aS / \ b b ``` Arbre 2 : ``` S / \ b SaS / / \ b a S / \ b b ```

4. Quel est le langage engendré par cette grammaire ?

Le langage engendré par cette grammaire est l’ensemble des mots de la forme aⁿbⁿaⁿbⁿ où n ≥ 0.

Exercice 2

Considérons la grammaire : R → R | R R → RR R → R* R → ( R ) R → a R → b

1. Que génère cette grammaire ?

Cette grammaire génère des expressions régulières composées de lettres a et b, incluant : - les lettres individuelles (a, b) - les répétitions (R*, RR) - les parenthèses pour regrouper des sous-expressions ((R)) - les concaténations (R R)

2. Montrer que cette grammaire est ambiguë

Exemple d’ambiguïté pour l’expression (a)b : Dérivation 1 : R ⇒ ( R ) ⇒ ( a ) ⇒ R R ⇒ a b Dérivation 2 : R ⇒ R R ⇒ ( R ) b ⇒ ( a ) b ⇒ a b

Exercice 3

On veut établir une grammaire d’expressions arithmétiques prenant en compte : 1. La priorité des opérateurs × et / sur les opérateurs + et – 2. L’écriture de parenthèses 3. L’utilisation d’identificateurs de variable 4. Une seule forme de nombre

1. Donner l’ensemble des terminaux de cette grammaire

Terminaux : - Nombres (ex : 25, 30) - Variables (ex : a, b) - Opérateurs : ×, /, +, – - Parentheses : (, ) - Espaces (optionnel pour la lisibilité) - Point-virgule (;) pour séparer les expressions (si nécessaire)

2. Donner une grammaire récursive à gauche

Exemple de grammaire récursive à gauche : E → T | E + T | E – T T → F | T × F | T / F F → N | V | ( E ) N → 0 | 1 | 2 | ... | 9 | N0 | N1 | N2 | ... | N9 V → a | b | ... | z | A | B | ... | Z

3. Donner une grammaire non récursive à gauche

Exemple de grammaire non récursive à gauche : E → T E' | T E' → + T E' | – T E' | ε T → F T' | F T' → × F T' | / F T' | ε F → N | V | ( E )

4. Donner l’arbre de dérivation correspondant à 25 × (a + 30 – 12 / 4)

Arbre de dérivation : ``` E / \ T E' / / \ F + T E' / / / \ N ( E ) F E' T / \ / / \ N V N 30 E' / / / / \ 25 a 12 – F / \ / \ / \ a 30 N 4 N / \ / \ 30 ε 4 ε ```

Exercice 4

Une 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.

1. Transformer la grammaire suivante pour la mettre sous forme FNC

Grammaire initiale : S → A | Bbb A → aB | bS | ε B → ABb | Bb | ε

Grammaire transformée en FNC : S → AS' | BbbS' S' → ε A → aB' | bS' A' → ε B' → ABbB'' | BbB'' B'' → ε

Explications supplémentaires : - Introduire un nouveau symbole S' pour gérer la production vide de S. - Remplacer les productions avec ε par des règles avec un symbole dédié (ex : A' → ε, B'' → ε). - Décomposer les règles pour respecter A → BC ou A → a.

2. Montrer que toute grammaire de type 2 peut être transformée en une grammaire FNC

Toute grammaire de type 2 (grammaire contextuelle libre) peut être transformée en FNC en utilisant les étapes suivantes : 1. Supprimer les productions vides (ε) en introduisant un nouveau symbole. 2. Supprimer les productions unitaires (A → B) sauf pour l’axiome. 3. Remplacer les productions de la forme A → aB ou A → Ba par des règles intermédiaires. 4. Normaliser les règles pour qu’elles soient de la forme A → BC ou A → a.

FAQ

Qu’est-ce qu’une grammaire ambiguë ?

Une grammaire est ambiguë si une phrase peut être dérivée de deux façons différentes, ce qui implique qu’il existe au moins deux arbres de dérivation distincts pour cette phrase.

Comment transformer une grammaire en FNC ?

Pour transformer une grammaire en FNC, il faut supprimer les productions unitaires, les productions avec plus de deux symboles, et gérer les productions vides en introduisant des symboles dédiés.

Quelle est la différence entre une dérivation gauche et droite ?

En dérivation gauche, on remplace toujours le symbole le plus à gauche, tandis qu’en dérivation droite, on remplace toujours le symbole le plus à droite.