Université de Bejaia
Département d’Informatique
Théorie des langages
Ce document contient le résumé (les affichages faits par semaine) de ce que nous avons fait en ligne
durant cette période de pandémie.
Les notions fondamentales que les étudiants doivent acquérir, dans cette partie du cours faite en
ligne, sont :
Comprendre les notions de base (Concaténation, miroir, etc.).
Trouver des grammaires qui génèrent un langage donné.
Trouver le langage généré par une grammaire donnée.
Déterminer le type des règles, des grammaires et des langages.
Trouver un AEF pour un langage de type 3 donné.
Trouver le langage (sous forme d’ensemble ou d’expression régulière) reconnu par un AEF
donné.
Transformer une expression régulière en AEF.
Transformer un AEF généralisé en AEF simple et déterministe.
NB1 : Les enseignants du module sont disponibles pour accompagner et répondre aux questions des
étudiants sur l’e-mail suivant, [email protected]
NB2 : Nous vous informons aussi qu’une page Facebook a été créée, nous y afficherons les questions
redondantes des étudiants avec nos réponses. Nous encourageons les étudiants à interagir entre eux sur
cette page. Nous l’avons nommée « Cours ThL, Informatique, Université de Bejaia ». Vous pourrez aussi
nous contacter sur cette page.
NB3 : Vous pouvez consulter le fichier ppt avec des explications sonores, enregistré sur le drive à partir du
lien suivant :
https://drive.google.com/file/d/1mGOTr-1BjtbZ9RIf9CYteUJjMoIt1fJa/view?usp=sharing
Travail à faire Semaine 1 :
Cours : Etudier de la page 4 jusqu’à la page 8 du support de cours
(Définition de la concaténation, définition de la longueur d’un mot, définition du miroir d’un mot,
définition de la puissance d’un mot, factorisation, définition d’un langage formel, opérations sur les
langages, propriétés).
TD : Exercice 1 et 2 de la série 1.
Travail à faire Semaine 2 :
Cours : Etudier de la page 8 jusqu’à la page 11 du support de cours
Le but est de maitriser la génération de langages avec des grammaires (L’un des aspects les plus importants
du module).
TD : Faire l'exercice 3 de la série 1, exercice 1 et 3 de la série 2.
PS : Nous notons que plusieurs grammaires différentes peuvent générer le même langage.
Solution TD
Travail à faire Semaine 3 :
Cours : Terminer le chapitre 1 du support de cours.
TD : Faire l'exercice 2, et terminer l’exo 3 de la série 2.
NB : Les langages restant de l’exo 3 sont relativement complexes.
Interrogation : Faire l’exercice donné et nous l'envoyer avant le 02 Mai à minuit,
en PDF.
NB: Nous affichons un algorithme qui permet de déterminer le type des règles et des
grammaires.
Dans les solutions des exercices, le type des règles est mis comme un nombre
encerclé au-dessus de la règle.
Travail à faire Semaine 5 :
Cours : étudier de la page 17 jusqu'à la page 23 , il faut absolument comprendre les
exemples corrigés des AEF. (Se focaliser sur la représentation graphique des AEF).
TD : Faire l'exo 1 de la série 3.
Travail à faire Semaine 6 :
Cours : étudier de la page 23 jusqu'à la page 25.
TD : L'exercice ExoS7 des exo supplémentaires, du langage Ls1 jusqu'à Ls8.
Travail à faire Semaine 7 :
Cours : Terminer le chapitre 2 (sans étudier la minimisation des AEF).
TD : Faire l'exo2 de la série 3. (Sans faite la question. 2 et 6, car elles incluent la
minimisation).
NB : on poursuit le module avec des séances en visio-conférences sur Zoom selon
les affichages.
