Td 3 langages de programmation Théorie des langages-tél...

Théorie des langages : Td 3 langages de programmation

Télécharger PDF

Université 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 w_n est un mot du langage L, composé de n caractères, alors |w_n|_a = |w_n|_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 w_n+2 sont obtenus comme suit :

— w_n+2 = a w_l b w_m (en utilisant S ⇒ aSbS)

— w_n+2 = b w_l a w_m (en utilisant S ⇒ bSaS)

Il est clair que l + m = n. En utilisant l’hypothèse de récurrence sur w_l et w_m, on remarque que H1 est vraie pour w_l et w_m. On a :

|w_n+2|_a = 1 + |w_l|_a + |w_m|_a

|w_n+2|_b = 1 + |w_l|_b + |w_m|_b

On conclut que |w_n+2|_a = |w_n+2|_b car |w_l|_a = |w_l|_b et |w_m|_a = |w_m|_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 w_l b w_m, avec l = k − 2 et m = n − k.

Si W existe, alors w_l et/ou w_m ne sont pas générés par la grammaire. Cela contredit l’hypothèse de récurrence pour w_l et/ou w_m, 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 w_k un mot du langage engendré par la grammaire obtenu après avoir appliqué k règles de production.

H : w_k est une expression régulière définie sur a et b. De plus, w_k 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 w₁ = a et w₁ = 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 :

w_n+1 =

w_iw_j (concaténation), ∀i, j > 0 avec i + j = n

w_i|w_j (disjonction), ∀i, j > 0 avec i + j = n

w_i∗ (fermeture), où i = n (1)

On note que H est vraie pour w_i et w_j. À partir de (1), on conclut que w_n+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 G₁, ou toute grammaire équivalente, ne gère pas la priorité de ∗ et / par rapport à + et −.

Soit la grammaire G₁ = (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 G₁ 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