Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF4223  Gr. 01
Titre : Langages formels
Session : Automne 2017  Horaire et local
Professeur : Godon, Maxime
1. Description du cours paraissant à l'annuaire :

Objectifs

Introduire l'étudiant aux différents modèles de calcul. Familiariser l'étudiant à la théorie des langages formels. Faire comprendre les limitations des ordinateurs.

Contenu

Langages réguliers et automates finis. Langages hors contexte et automates à pile. Grammaires contextuelles. Hiérarchie de Chomsky. Machines de Turing. Hypothèse de Church. Calculabilité et déterminisme. Problèmes indécidables. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine.
2. Objectifs spécifiques du cours :
  1. Initier l'étudiant aux fondements théoriques de l'informatique ;
  2. Le familiariser avec la théorie des langages formels et à son application à la construction des logiciels, des langages de programmation et ses compilateurs ;
  3. Familiariser l'étudiant avec les limites posées par les ordinateurs contemporains: introduire la classe de problèmes indécidables (impossibles à résoudre) et la classe de fonctions incalculables. Problème de déterminisme en informatique. L'étudiant se rendra compte de ce qui est possible et de ce qui n'est pas possible de réaliser à l'aide des ordinateurs.
3. Stratégies pédagogiques :
  • Cours magistraux
  • Séances d'exercices
  • Devoirs (2)
4. Heures de disponibilité ou modalités pour rendez-vous :
  • Les lundis, entre 15:45 et 18:45 heures (pendant les cours)
  • Les mercredis, entre 16:00 et 18:00 heures (pendant les séances d'exercices)
  • Rendez-vous par courriel à l'adresse : maxime.godon@uqo.ca
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1   
  • Préliminaires
  • Alphabets
  • Langages
  • Opérations sur symboles et langages
  • Exercices
  • Séance d'exercices 1 (13 septembre 2017) : Opérations sur les symboles et langages.

11 sept. 2017 
2   
  • Matrices de transition
  • Automates finis non déterministes
  • Détermination d'automates finis
  • Exercices
  • Séance d'exercices 2 (20 septembre 2017) : Détermination des automates finis.

18 sept. 2017 
3   
  • Minimisation d'automates finis déterministes
  • Exercices
  • Séance d'exercices 3 (27 septembre 2017) : Minimisation des automates finis. Construction des automates finis à partir des expressions régulières.

25 sept. 2017 
4   
  • Lemmes de pompage pour langages réguliers
  • Exercices
  • Séance d'exercices 4 (4 octobre 2017) : Lemme de pompage.

02 oct. 2017 
5    Semaine d'études 09 oct. 2017 
6   
  • Équivalences d'automates finis et expressions régulières
  • Passage des automates finis aux expressions régulières
  • Séance d'exercices 5 (18 octobre 2017) : Équivalences d'automates finis et expressions régulières.

16 oct. 2017 
7    Examen de mi-session 23 oct. 2017 
8   
  • Grammaire hors-contexte
  • Dérivations et arbres de dérivation

Séance d'exercices 6 (1er novembre 2017) : Introduction aux grammaires hors- contexte.

30 oct. 2017 
9   
  • Formes normales
  • Forme normale de Chomsky
  • Forme normale de Greibach

Séance d'exercices 7 (8 novembre 2017) : Formes normales.

06 nov. 2017 
10   
  • Automates à pile (AP)
  • Analyse syntaxique descendante et ascendante
  • Exercices

Séance d'exercices 8 (15 novembre 2017): Automates à pile.

13 nov. 2017 
11   
  • Automates à pile déterministes
  • Propriétés des langages hors-contexte
  • Lemme de pompage
  • Langages réguliers et langages hors-contexte (LHC)

Séance d'exercices 9 (15 novembre 2017) : Lemme de pompage.

20 nov. 2017 
12   
  • Propriétés de fermeture
  • Algorithmes de décision pour LHC non-déterministes

Séance d'exercices 10 (29 novembre 2017): Révision: langages hors-contexte

27 nov. 2017 
13   
  • Machines de Turing
  • Langages récursifs et récursivement énumérables
  • Machine de Turing comme un calculateur de fonctions entières
  • Modifications de machines de Turing. Machines de Turing non-déterministes
  • Hypothèse de Church
  • Hiérarchie de Chomsky
  • Séance d'exercices 11 (6 décembre 2017) : Machine de Turing.

04 déc. 2017 
14   
  • Introduction aux problèmes indécidables
  • Problèmes indécidables et machines de Turing ; Problème d'arrêt
  • Problème de correspondance de Post
  • Problème indécidables pour langages hors-contexte
  • Révision
  • Séance d'exercices 12 (13 décembre 2017) : Révision.

11 déc. 2017 
15    Examen final. 18 déc. 2017 
6. Évaluation du cours :
  • Devoirs : 20 % (10 % chacun)
  • Examen mi-session : 35 %
  • Examen final : 45 %
7. Politiques départementales et institutionnelles :
8. Principales références :
Bibliographie de base
  1. CZYZOWICZ, J.; Langages formels, INF 4223 (notes de cours), UQO, septembre 2011

Bibliographie de références

  1. SIPSER, M.; Introduction to the Theory of Computing, International Thomson Publishing, 2005
  2. COHEN, D.; Introduction to Computer Theory, John Wiley & Sons, 1996
  3. HOPCROFT, J.E. MOTWANI, R. & ULLMAN, J.D.; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006
  4. FLOYD, R. & BEIGEL, R.; Le langage des machines: introduction à la calculabilité et aux langages formels, International Thomson Publishing France, 1995
  5. BROOKSHEAR, J.G.; Theory of computation: formal languages, automata, and complexity, Benjamin/Cummings, 1989
  6. LEWIS, H.R. & PAPADIMITRIOU, C.H.; Elements of the Theory of Computation, Prentice-Hall, 1997

9. Page Web du cours :
https://moodle.uqo.ca