Théorie des langages : Td 1 langages formels
Télécharger PDFExercice 1
(6 pts) Soient les grammaires G1, G2 et G3 suivantes :
1. Déterminer le type de chaque règle, puis le type de chaque grammaire.
La grammaire G1 :
- type 2
- type 2
- type 3
- type 0
- type 1
- type 1
- type 1
Le type de G1 est 0.
La grammaire G2 :
- type 3
- type 3
- type 1
- type 3
Le type de G2 est 0.
La grammaire G3 :
- type 3
- type 3
- type 3
Le type de G3 est 2.
2. Déterminer le langage généré par chaque grammaire.
Le langage généré par la grammaire G1 est :
Le langage généré par la grammaire G2 est :
Le langage généré par la grammaire G3 est :
Exercice 2
(7 pts) Soient les langages suivants : L1, L2, L3.
1. Donner une expression régulière pour L1.
Réponse :
2. Trouver les automates à états finis simples et déterministes (AEF) reconnaissant les langages L1 et L2.
L'AEF reconnaissant L1 :
L'AEF reconnaissant L2 :
3. Trouver les grammaires qui génèrent L1, L2 et L3.
La grammaire qui génère L1 :
La grammaire qui génère L2 :
La grammaire qui génère L3 :
4. Donner une condition suffisante mais pas nécessaire sur « n » pour que L3 soit reconnu.
Réponse : n ≥ 1.
5. Calculer L1 ∪ L2, L1 ∩ L2 et L1 \ L2.
Réponse :
6. Donner une expression régulière qui dénote le langage reconnu par l'AEF suivant.
Réponse :
Exercice 3
(7 pts) Soient les langages suivants : L4, L5.
1. Trouver les grammaires qui génèrent chaque langage.
La grammaire qui génère L4 :
La grammaire qui génère L5 :
2. Calculer le langage L4 ∩ L5, puis trouver la grammaire qui génère ce langage.
Le langage L4 ∩ L5 est :
La grammaire qui génère le langage L4 ∩ L5 est :
3. Trouver la grammaire qui génère le langage L4 ∪ L5.
À partir de l'axiome S, on peut générer un mot de L4 (via S1) ou un mot de L5 (via S2).
La grammaire qui génère le langage L4 ∪ L5 est :
FAQ
Qu’est-ce qu’une grammaire de type 0 ?
Une grammaire de type 0, ou grammaire non restreinte, est une grammaire formelle où les règles peuvent être de la forme α → β, avec α et β des chaînes de symboles non vides, sans restriction sur la longueur ou la structure des règles.
Comment reconnaître un langage avec un automate à états finis (AEF) ?
Un automate à états finis reconnaît un langage en acceptant les chaînes de caractères qui suivent une séquence de transitions définie entre ses états. Chaque état représente une configuration possible de lecture, et les transitions dépendent des symboles lus.
Quelle est la différence entre une grammaire de type 1 et une grammaire de type 2 ?
Une grammaire de type 1, ou grammaire contextuelle, permet des règles où le côté gauche a au moins autant de symboles que le côté droit. Une grammaire de type 2, ou grammaire sans contexte, a des règles de la forme A → α, où A est un symbole non terminal et α une chaîne de symboles.