Théorie des langages : Td 3 langages de programmation
Télécharger PDFUniversité de Technologie de Compiègne - Théorie des Langages de Programmation : TD3
Exercice 1
On donne deux dérivations gauche du mot abab :
D1 : S ⇒ LM aSbS ⇒ LM abSaSbS ⇒ LM abaSbS ⇒ LM ababS ⇒ LM abab
D2 : S ⇒ LM aSbS ⇒ LM abS ⇒ LM abaSbS ⇒ LM ababS ⇒ LM abab
Cette grammaire est ambiguë, car il existe deux dérivations gauche pour le mot abab.
On donne également deux dérivations droite pour le mot abab :
D1 : S ⇒ RM aSbS ⇒ RM aSb ⇒ RM abSaSb ⇒ RM abSab ⇒ RM abab
D2 : S ⇒ RM aSbS ⇒ RM aSbaSbS ⇒ RM aSbaSb ⇒ RM aSbab ⇒ RM abab
Cette grammaire génère le langage L composé de toutes les chaînes sur a et b telles que le nombre de a est égal au nombre de b.
Démonstration
Soit l’hypothèse suivante, H : Le langage L est composé de n’importe quel mot sur a et b tel que le nombre de a est égal au nombre de b. On décompose cette hypothèse en deux parties :
— H1 : Si wn est un mot du langage L, composé de n caractères, alors |wn|a = |wn|b (le nombre de a est égal au nombre de b). En conséquence, n est pair.
— H2 : La grammaire génère tous les mots possibles sur a et b tels que la condition H1 est vraie.
Vérification :
— Pour n = 0, la grammaire peut générer ε (le mot vide).
— Pour n = 2, la grammaire peut générer :
S ⇒ LM aSbS ⇒ LM abS ⇒ LM ab
S ⇒ LM bSaS ⇒ LM baS ⇒ LM ba
Il est à noter qu’il existe 4 mots possibles sur a et b de longueur 2 : aa, ab, ba, bb. Seuls ab et ba vérifient la condition H1. En conséquence, H1 et H2 sont vraies pour n = 0 et n = 2.
On suppose que H est vraie (en particulier H1 et H2) jusqu’à l’ordre n. On démontre ensuite H pour l’ordre n + 2.
Les mots wn+2 sont obtenus comme suit :
— wn+2 = a wl b wm (en utilisant S ⇒ aSbS)
— wn+2 = b wl a wm (en utilisant S ⇒ bSaS)
Il est clair que l + m = n. En utilisant l’hypothèse de récurrence sur wl et wm, on remarque que H1 est vraie pour wl et wm. On a :
|wn+2|a = 1 + |wl|a + |wm|a
|wn+2|b = 1 + |wl|b + |wm|b
On conclut que |wn+2|a = |wn+2|b car |wl|a = |wl|b et |wm|a = |wm|b (hypothèse de récurrence).
Pour la deuxième partie de la démonstration, supposons qu’il existe un mot W de n + 2 caractères ayant le même nombre de a que de b, mais qui n’est pas généré par la grammaire.
Supposons que W commence par a (le même raisonnement est valide pour un mot commençant par b). Soit k le plus petit indice d’un caractère b tel que le nombre de a dans W[1..k] est égal au nombre de b dans W[1..k].
Exemple : considérons le mot "aababbab", on a k = 6, W[1..6] = "aababb". Dans W[1..6], le nombre de a est égal au nombre de b et est égal à 3.
En tenant compte que le premier caractère de W est a et que le k-ème caractère est b, on peut écrire W de la manière suivante : W = a wl b wm, avec l = k − 2 et m = n − k.
Si W existe, alors wl et/ou wm ne sont pas générés par la grammaire. Cela contredit l’hypothèse de récurrence pour wl et/ou wm, où H est vrai car l, m ≤ n.
Exercice 2
Précision : l’ensemble des terminaux de la grammaire est T = {(, ), a, b, ∗, |}.
1. Cette grammaire génère des expressions régulières exclusivement sur a et b (impossible d’avoir ε). L’expression peut contenir les méta-symboles parenthèses et peut être composée des trois opérateurs : concaténation, disjonction et fermeture.
2. Démonstration : Soit wk un mot du langage engendré par la grammaire obtenu après avoir appliqué k règles de production.
H : wk est une expression régulière définie sur a et b. De plus, wk peut contenir les méta-symboles parenthèses et peut être composée des trois opérateurs : concaténation, disjonction et fermeture.
Vérification : On remarque que la grammaire génère w1 = a et w1 = b, deux expressions régulières obtenues après avoir appliqué une règle de production (une des deux dernières).
On suppose que H est vraie, ∀k ≤ n. On démontre que H est vraie pour k = n + 1. En utilisant les quatre premières règles de production de la grammaire, on remarque que :
wn+1 =
wiwj (concaténation), ∀i, j > 0 avec i + j = n
wi|wj (disjonction), ∀i, j > 0 avec i + j = n
wi∗ (fermeture), où i = n (1)
On note que H est vraie pour wi et wj. À partir de (1), on conclut que wn+1 est bien une expression régulière vérifiant les conditions listées ci-dessus.
2. On considère le mot aba, et on donne ces deux dérivations :
D1 : R ⇒ LM RR ⇒ LM aR ⇒ LM aRR ⇒ LM abR ⇒ LM aba
D2 : R ⇒ LM RRR ⇒ LM aRR ⇒ LM abR ⇒ LM aba
Exercice 3
1. L’ensemble des terminaux de cette grammaire est T = {∗, /, +, −, (, ), id, nb}.
2. Soit la grammaire G = (T = {∗, /, +, −, (, ), id, nb}, V = {E, T, F}, E, P), avec les règles de production suivantes :
E ⇒ E + T | E − T | T
T ⇒ T ∗ F | T / F | F
F ⇒ (E) | id | nb
Attention : la grammaire suivante G1, ou toute grammaire équivalente, ne gère pas la priorité de ∗ et / par rapport à + et −.
Soit la grammaire G1 = (T = {∗, /, +, −, (, ), id, nb}, V = {E}, E, P), avec les règles de production suivantes :
E ⇒ E + E | E − E | E ∗ E | E / E
E ⇒ (E) | nb | id
La grammaire G1 est ambiguë. On donne deux dérivations gauche du mot "id + id ∗ id" :
D1 : E ⇒ LM E + E ⇒ LM id + E ⇒ LM id + E ∗ E ⇒ LM id + id ∗ E ⇒ LM id + id ∗ id
D2 : E ⇒ LM E ∗ E ⇒ LM E + E ∗ E ⇒ LM id + E ∗ E ⇒ LM id + id ∗ E ⇒ LM id + id ∗ id
Si on remplace tous les id par la valeur 5, le résultat de D1 est 30 alors que le résultat de D2