Scribd
Importer
10 vues1 page

Exercices de grammaire algébrique THL 2024

Transféré par

Ammar Dridi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
10 vues1 page

Exercices de grammaire algébrique THL 2024

Transféré par

Ammar Dridi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Ecole Supérieure en Sciences et Technologies de l'Informatique et Numérique( ESTIN)

Annee 2024/2025

Serie de TD N°5, Module Théorie des Langages (THL)


(Grammaire hors contexte et automates à pile)

Exercice1

Soit une grammaire algébrique définie par les huit règles de productions suivantes :

S → ABC A → 0A/1 B → 0B/1B/0 C →C11/ ε

Donnez une dérivation gauche produisant la chaine «01011» avec S : est l’axiome

Exercice2

Soit une grammaire algébrique G (hors contexte) définie par ses règles de productions:

S → aAB, A → bBb, B → A/ ε

1. Donnez les deux dérivations gauche et droite produisant la chaine « abbbb »


2. Le mot est-il validé par G ?

Exercice3

On considère la grammaire G suivante : G=(T, N, S, P) où P : S → aS|aSbS|ε

1. Déterminer les paramètres de G?


2. Montrer que le mot aab contient deux :
Arbres de dérivations
Dérivations droite
Dérivations gauche
3. La grammaire est-elle ambigüe?

Exercice 4
Soit la grammaire G = (T, N, P, S) Où N = {S}, T= {a, b} et P = {S → aSa|bSb|ε}
Soit une autre grammaire G′ = (T, N, P′, S), avec P′ = {S → aSa|bSb| ε} ∪{S → SS}

1. Montrez que le mot «aabaab»∈ L (G′).


2. Montrez ensuite que G′ est ambigüe.
3. Quel est le langage engendré par G ? Démontrez
4. Pourquoi G n'est pas ambigüe ?

Exercice 5
Soit la grammaire G de règles de production suivantes :
P : S → if b then S else S| if b then S| a
1. Donner les paramètres de la grammaire
2. Montrer que la grammaire est ambigüe.

Vous aimerez peut-être aussi