Scribd
Importer
47 vues3 pages

Corrigé Exercice Théorie des Langages

Ce document contient les corrigés de plusieurs exercices sur la théorie des langages. Il présente les solutions détaillées à des exercices portant sur la reconnaissance de langages réguliers, la déterminisation d'automates finis et la construction de graphes de dérivation.

Transféré par

seyfeddine.hammami
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
47 vues3 pages

Corrigé Exercice Théorie des Langages

Ce document contient les corrigés de plusieurs exercices sur la théorie des langages. Il présente les solutions détaillées à des exercices portant sur la reconnaissance de langages réguliers, la déterminisation d'automates finis et la construction de graphes de dérivation.

Transféré par

seyfeddine.hammami
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

Université Chadli Bendjedid – El Tarf Module : Théorie des Langages

Faculté des Sciences et de la Technologie Durée : 1h15


Département d’Informatique Barème : /20

17/04/2017

EMD Théorie des Langages


Corrigé

Exercice 1 (4pts)
1. (𝑎 + 𝑏)∗ 𝑎(𝑎 + 𝑏)∗ : ensemble de tous les mots contenant au moins a (0.5pts)
𝑎, 𝑏 𝑎, 𝑏

𝑎 (0.5pts)

2. 𝑎𝑏 ∗ + 𝑏 : ensemble des mots contenant un seul 𝑎 et bornés par 𝑎 et 𝑏 (commençant par 𝑎 et se


terminant par 𝑏) (0.5pts)
𝑏
(0.5pts)
𝑎 𝑏

3. (𝑎 + 𝑐)∗ 𝑎𝑐(𝑏 + 𝑑)∗ 𝑎𝑏𝑎 : ensemble des mots contenant au moins une occurrence de la sous-
chaine 𝑎𝑐 et se terminant par la sous chaine 𝑎𝑏𝑎 (0.5pts)
𝑎, 𝑐 𝑏, 𝑑 (0.5pts)

𝑎 𝑐 𝑎 𝑏 𝑎

4. 𝑏 ∗ 𝑎(𝑎 + 𝑏)∗ 𝑏𝑎∗ : ensemble des mots contenant au moins une occurrence de 𝑎 et une occurrence
de 𝑏

𝑏 𝑎, 𝑏 𝑎
(0.5pts)
𝑎 𝑏

Exercice 3 (12pts)
a. Déterminisation : (2.5 pts)
𝛿(1, 𝜀) = 3 𝛿(2, 𝜀) = 3 𝛿(4, 𝜀) = 5 𝛿(5, 𝜀) = 6 𝛿(5, 𝜀) = 4
𝛿(3, 𝑎) = 5 𝛿(3, 𝑎) = 5 𝛿(5, 𝑎) = 5 𝛿(6, 𝑏) = 6 𝛿(4, 𝑏) = 5
𝜹(𝟏, 𝒂) = 𝟓 𝜹(𝟐, 𝒂) = 𝟓 𝜹(𝟒, 𝒂) = 𝟓 𝜹(𝟓, 𝒃) = 𝟔 𝜹(𝟓, 𝒃) = 𝟓
ε, a
2 4
a a

ε, b b ε, b
1
a
a
ε,b 3 5
a

a b
1 {1,2} 3
2 {4,5} {3,5} (1.0pts)
3 5 ∅
4 {5,6} 5
5 {5,6} {2,5,6}
*6 ∅ 6

a. Construire un automate 𝑇3 déterministe, équivalent à 𝑇2 . (3pts)

a b
1 {1,2} 3
{1,2} {1,2,4,5} {3,5}
3 5 ∅
{1,2,4,5} {1,2,4,5,6} {2,3,5,6}
{3,5} {5,6} {2,5,6}
5 {5,6} {2,5,6}
∗ {1,2,4,5,6} {1,2,4,5,6} {2,3,5,6}
∗ {2,3,5,6} {4,5,6} {2,3,5,6}
∗ {5,6} {5,6} {2,5,6}
∗ {2,5,6} {4,5,6} {2,3,5,6}
∗ {4,5,6} {5,6} {2,5,6}
(2pts)
a b
1 2 3
2 4 5
3 6 ∅
4 7 8
5 9 10
6 9 10
∗7 7 8
∗8 11 8
∗9 9 10
∗ 10 11 8
∗ 11 9 10

Exercice 4 (4pts)
a. 𝐺1 = (𝛴, 𝑉, 𝑆, 𝑅) 𝑎𝑣𝑒𝑐 𝛴 = {𝑎, 𝑏, 𝑐}, 𝑉 = {𝑆, 𝐴}, 𝑆 = {𝑆},
𝑅 = {𝑆 → 𝑎𝐴𝑎𝑐} ∪ {𝐴 → 𝑆𝑏|𝑏𝑏}
Ensemble des mots commençant par 𝒂 et se terminant par la sous-chaine 𝒂𝒄 (2pts)
b. 𝐺2 = (𝛴, 𝑉, 𝑆, 𝑅) 𝑎𝑣𝑒𝑐 𝛴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝑉 = {𝑆, 𝑋}, 𝑆 = {𝑆},
𝑅 = {𝑆 → 𝑏𝑋} ∪ {𝑋 → 𝑋𝑏𝑎|𝑐𝑎|𝑑𝑎}
Ensemble des mots commençant par 𝒃 et se terminant par 𝒂 (2pts)

Common questions

Alimenté par l’IA

The language defined by the regular expression (a+b)*a(a+b)* consists of all words that contain at least one 'a' .

Transition rules like δ(5, ε) = 6 imply an epsilon transition from state 5 to 6, enabling state change without symbol consumption. This affects the process by introducing non-determinism, offering multiple pathway options and necessitating strategies for efficient determinization to maintain equivalent language recognition .

Grammar G2 has rules R = {S→bX} ∪ {X→Xba|ca|da}, generating words that start with 'b' and end with 'a', exploiting non-terminal X to extend word sequences through productions of 'Xba', 'ca', and 'da' .

The initial states and transitions are represented using sets in the transition table, like state 1 → {1,2}, indicating potential moves. In determinism, each input/state pair describes a unique next state, while non-determinism allows multiple possible next states, such as the ε-transitions setting up multiple paths .

Epsilon transitions, like δ(1, ε) = 3 and δ(2, ε) = 3, allow states to change without consuming any input symbol, enabling conversions that simplify the automaton without modifying the language it recognizes. They are crucial for achieving a deterministic automaton by resolving non-determinism .

The process of determinization involves defining transition functions δ that determine state changes based on input symbols and epsilon transitions. For example, δ(1, ε) = 3, δ(3, a) = 5, indicating that an epsilon transition can move from state 1 to 3, and from state 3 receiving 'a' to state 5 .

Regular expressions like a(b*)+b describe languages where words begin and end with specified patterns. Here, words consist of a single 'a', followed potentially by any number of 'b's, culminating in a single 'b', emphasizing bounded beginnings and endings .

The set (a+c)*ac(b+d)*aba requires at least one occurrence of the substring 'ac' and ends with the substring 'aba', allowing any combination of 'a' and 'c' before, and 'b' and 'd' after 'ac', but constrained by needing 'aba' as the terminus .

Grammar G1 has the set of rules R = {S→aAa𝑐} ∪ {A→Sb|bb}. It generates words that start with 'a' and end with 'ac', using non-terminal A for creating complex sequences by either appending 'Sb' or 'bb' in between .

G1 derives words by producing sequences starting with 'a' and ending with 'ac', leveraging rule interdependencies like S→aAa𝑐 and A→Sb|bb, whereas G2 generates structures starting with 'b' and ending with 'a', using rules like S→bX and X→Xba|ca|da, highlighting distinct syntactical frameworks .

Vous aimerez peut-être aussi