Scribd
Importer
506 vues1 page

Travaux Dirigés 3: Exercice1

Transféré par

hafsa ladhasse
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
506 vues1 page

Travaux Dirigés 3: Exercice1

Transféré par

hafsa ladhasse
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

Travaux dirigés 3

Exercice1
Donner tous les mots de tailles 0, 1, 2, 3, et 4 des langages réguliers suivants :
 (a + ba) ∗
 a(aa + b(ab)∗ 𝑎)∗ . 𝑎
Exercice2
Sur l’alphabet {a, b}, donner une expression régulière pour
 Le langage des mots qui entre deux occurrences de la lettre a ont un nombre pair de b.
 Le langage des mots tels que toutes les (éventuelles) occurrences de a précèdent toutes
les (éventuelles) occurrences de b.
Exercice 3
Donnez une expression régulière qui accepte chacun des langages suivants (définis sur
l’alphabet Σ= {0,1}) :
 Toutes les chaînes qui se terminent par 00.
 Toutes les chaînes dont le 10ème symbole, compté à partir de la fin de la chaîne, est un
1.
 Ensemble de toutes les chaînes dans lesquelles chaque paire de 0 apparaît devant une
paire de 1.
 Ensemble de toutes les chaînes ne contenant pas 101.
 Tous les nombres binaires divisibles par 4.
Exercice4
Soit l'alphabet Ω = {a,b}, Donner les expressions régulières correspondants aux langages
suivants :

 L1 = {𝜖, a, b, ab}
 L2 = {bn / n>=2, n étant un entier}
 L3 = {w∈{a,b}*, tel que w contient seulement 3b, le reste c'est des a's}
 L4 = { w∈{a,b}*, tel que w contient un nombre de a divisible par 3}
 L5 = { w∈{a,b}*, tel que w contient un nombre paire de a}
 L6 = {w∈{a,b}*, tel que w contient un nombre impaire de b}
Exercice5
Prouver les équivalences suivantes :

 (a+b) + (a+b)(a+b)∗ +∅∗ ≡ (a+b)∗


 (x+y)∅+ (x+y)∅∗ + ((x+y)∗∅∗)∗ ≡ (x+y)∗

Vous aimerez peut-être aussi