Scribd
Importer
127 vues2 pages

Exercices sur les langages formels

Ce document contient plusieurs exercices sur la théorie des langages formels. Les exercices portent sur des opérations sur langages comme l'intersection, l'union et la concaténation. Ils impliquent également des propriétés comme la parité de la longueur des mots.

Transféré par

Oumaima Ziat
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
127 vues2 pages

Exercices sur les langages formels

Ce document contient plusieurs exercices sur la théorie des langages formels. Les exercices portent sur des opérations sur langages comme l'intersection, l'union et la concaténation. Ils impliquent également des propriétés comme la parité de la longueur des mots.

Transféré par

Oumaima Ziat
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 2

Exercice 1
Quels sont les deux langages dont la fermeture par l’étoile donne le langage uniquement composé du
mot vide ε ?
Les mots suivants sont-ils générés par le langage (𝑎𝑏∗ )𝑏 ∗ ∶ 𝜀, 𝑎, 𝑎𝑎, 𝑏𝑎, 𝑎𝑏𝑏𝑏, 𝑎𝑏𝑎𝑏𝑏, 𝑏𝑎𝑏𝑎 ? Même
question avec le langage (𝑎𝑏)∗ 𝑏 ∗ .
Exercice 2
On considère l’alphabet X = {a,b}.
Donner les langages correspondant aux propriétés suivantes :
1. Les mots qui ne contiennent aucun b ;
2. Les mots qui ne contiennent pas ab ;
3. Les mots qui contiennent au moins un a ;
4. Les mots de longueur paire ;
5. Les mots de longueur est un multiple de 3 ou 5.
Exercice 3
On considère l’alphabet X = {a, b, c}.
1. Calculez les ensembles X0, X1 et X2
2. Pour chacun des ensembles suivants, caractérisez𝐿∗1 , et calculez 𝐿1 ∩ 𝐿2 , 𝐿1 ∪ 𝐿2 , 𝐿1 . 𝐿2 , 𝐿2 . 𝐿1
𝐿1 = {𝑎𝑏, 𝑏𝑏} et 𝐿2 = {a,ab,bbc, ca}

𝐿1 = {ε} et 𝐿2 = {𝑏𝑏𝑐, 𝑐𝑎}


𝐿1 = ∅ et 𝐿2 = {bbc, ca}
𝐿1 = {𝑎𝑏, 𝑏𝑏} et 𝐿2 = 𝑋 ∗
Exercice 4
On considère l’alphabet X = {a,b}, et les langages L1 et L2 suivants :
𝐿1 = {𝑎𝑛 𝑏𝑛 |n ∈ N}
𝐿2 = {𝑏𝑛 𝑎𝑛 |n ∈ N}

Calculez 𝐿1 ∩ 𝐿2 , 𝐿1 ∪ 𝐿2 , 𝐿1 . 𝐿2 , 𝐿2 . 𝐿1 , 𝐿21 .
Exercice 5
1. Montrez que L.(L1 ∩ L2) ⊆ L.L1 ∩ L.L2.
Exercice 6
On considère des langages sur un alphabet X quelconque. Soient les deux langages suivants :
𝐿𝑝 = {w | |w| est paire}

𝐿𝑖 = {w | |w| est impaire}

• Montrez que 𝐿2𝑝 = 𝐿𝑝


• Montrez que 𝐿𝑝 . 𝐿𝑖 = 𝐿𝑖 . 𝐿𝑝 = 𝐿𝑖

Exercice 7

Soit Σ = {0, 1}, démontrez que les deux langages suivants sont réguliers :

1. L’ensemble des mots composés d’un nombre arbitraire de 1, suivis de 01, suivis d’un nombre
arbitraire de 0.
2. L’ensemble des nombres binaires impairs.

Vous aimerez peut-être aussi