Scribd
Importer
51 vues2 pages

TD1 Exercice 1: M.gaye@univ-Zig - SN

Le document présente un TD pour la Licence 3 en Informatique à l'Université Assane Seck de Ziguinchor, axé sur la théorie des langages et la compilation. Il contient plusieurs exercices demandant de déterminer des mots selon des expressions régulières et de créer des expressions pour divers langages. Les exercices couvrent des sujets tels que les mots de longueur spécifique, les octets, et les représentations numériques.

Transféré par

ndeyeawambodji29
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
51 vues2 pages

TD1 Exercice 1: M.gaye@univ-Zig - SN

Le document présente un TD pour la Licence 3 en Informatique à l'Université Assane Seck de Ziguinchor, axé sur la théorie des langages et la compilation. Il contient plusieurs exercices demandant de déterminer des mots selon des expressions régulières et de créer des expressions pour divers langages. Les exercices couvrent des sujets tels que les mots de longueur spécifique, les octets, et les représentations numériques.

Transféré par

ndeyeawambodji29
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é Assane Seck de Ziguinchor Année universitaire 2023-2024

UFR des Sciences et Technologies


Département de Mathématiques
----------------------
Licence 3 en Informatique
Unité d’Enseignement : Théorie des langages et compilation
Élément Constitutif : Théorie des langages
---------------------
Responsable CM : Mouhamadou Gaye
TD-TP : Mouhamadou GAYE

TD 1

Exercice 1
Donner tous les mots de longueur inférieure ou égale à 3 et donner ensuite une caractérisation
de l’ensemble.
A = 0(0 + 1)∗
B = (0 + 1)(0 + 1)∗
C = 0(0 + 1)∗0 + 1(0 + 1)∗1
D = (0 + 01)∗
E = (0 + 1)∗ (00 + 11)(0 + 1)∗
F = (0 + ε)(10)∗ (1 + ε)

Exercice 2
Déterminer tous les mots de longueur maximale 4 qui appartiennent au langage dénoté par
chacune des expressions régulières suivantes :
1. (b+ba)∗
2. ab∗ +b
3. (a+b)∗abb
4. (a+ε)∗dd∗
5. (ad +ε)∗d∗
6. a∗(b+c)d∗

Exercice 3
Donner, quand c’est possible, une expression régulière décrivant les langages suivants.
1. l’ensemble de tous les octets sur Σ = {0, 1} ;
2. les mots sur Σ = {0, 1} qui se terminent par 011 ;
3. les mots sur Σ = {0, 1} qui contiennent le facteur 101 ; 1
4. les représentations binaires des nombres impairs (sans 0 inutile en tête) ;
5. l’ensemble des mots de Dyck ;
6. les mots sur Σ = {0, 1} qui ont autant de 0 que de 1

Exercice 4
1. Donner une expression régulière du langage formé des mots sur Σ = {a, b, c} qui ne
contiennent pas deux a consécutifs.
2. Donner une expression régulière du langage formé des mots sur Σ = {a, b} qui
contiennent le facteur aa exactement une fois.

Dr Mouhamadou GAYE 1 [Link]@[Link]


3. Donner une expression régulière du langage formé des mots sur Σ = {a, b, c} qui
débutent par a, contiennent exactement deux b et se terminent par cc.
4. Donner une expression régulière du langage formé des mots sur Σ = {a, b, c} qui
contiennent un nombre de a divisible par 3.
5. Donner une expression régulière du langage formé des mots sur Σ = {a, b} de
longueur impaire et qui contiennent le facteur bb.
6. Donner une expression régulière du langage formé des mots sur Σ = {a, b} ayant au
plus trois a. Donner une expression régulière du langage formé des mots sur Σ = {a, b,
c} qui contiennent un nombre impair d’occurrences du facteur ab.
7. Donner une expression régulière du langage formé des représentations en base 3 des
nombres pairs.
8. Donner une expression régulière du langage formé des représentations en base 10 des
nombres multiples de 5.

Exercice 5
Soit Σ = {0, 1}. On appelle mot binaire un mot sur l’alphabet Σ, et mot binaire normalisé un
mot binaire qui soit commence par 1, soit est exactement égal à 0.
Montrer que le langage Ln = {0, 1, 10, 11, 100, 101, . . .} des mots binaires normalisés est
rationnel en exhibant directement une expression régulière qui le dénote,

Dr Mouhamadou GAYE 2 [Link]@[Link]

Vous aimerez peut-être aussi