Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF4223  Gr. 01
Titre : Langages formels
Session : Hiver 2019  Horaire et local
Professeur : Abd-Ali, Jamal
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.

Descriptif – Annuaire

2. Objectifs spécifiques du cours :
  1. Initier l'étudiant(e) aux fondements théoriques de l'informatique;
  2. Familiariser l'étudiant(e) 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(e) 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(e) se rendra compte de ce qu’il 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 jeudis entre 12 h et 13 h sur rendez-vous 24 heures d’avance.

5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1   
  • Expressions régulières et automates finis
    • Préliminaires
    • Alphabets
    • Langages
    • Opérations sur symboles et langages
    • Exercices

Travaux dirigés 1 (jeudi 17 janvier) : Opérations sur les symboles et langages.

 11 jan. 2019 
2   

  • Matrices de transition
  • Automates finis non déterministes
  • Détermination d'automates finis
  • Exercices

Travaux dirigés 2 (24 janvier) : Détermination des automates finis.

 18 jan. 2019 
3   
  • Minimisation d'automates finis déterministes
  • Exercices

Travaux dirigés 3 (31 janvier) : Minimisation des automates finis. Construction des automates finis à partir des expressions régulières.

 25 jan. 2019 
4   
  • Lemmes de pompage pour langages réguliers
  • Exercices

Travaux dirigés 4 (07 février) : Lemme de pompage.

 01 fév. 2019 
5   
  • Équivalences d'automates finis et expressions régulières
  • Passage des automates finis aux expressions régulières

Travaux dirigés 5 (14 février) : Équivalences d'automates finis et expressions régulières.

 08 fév. 2019 
6   
  • Grammaire hors-contexte
    • Dérivations et arbres de dérivation

Travaux dirigés 6 (21 février) : Introduction aux grammaires hors-contexte.

 15 fév. 2019 
7   
  • Formes normales
  • Forme normale de Chomsky
  • Forme normale de Greibach

Travaux dirigés 7 (28 février) : Formes normales.

 22 fév. 2019 
8   

Examen de mi-session

 01 mars 2019 
9   

Semaine d'études

 08 mars 2019 
10   
  • Grammaire hors-contexte et Automates à pile
    • Automates à pile (AP)
    • Analyse syntaxique descendante et ascendante
    • Exercices

Travaux dirigés 8 (21 mars) : Automates à pile.

 15 mars 2019 
11   
  • Grammaire hors-contexte et Automates à pile (suite)
    • Automates à pile déterministes
  • Propriétés des langages hors-contexte
    • Lemme de pompage
    • Langages réguliers et langages hors-contexte (LHC)

Travaux dirigés 9 (28 mars) : Lemme de pompage.

 22 mars 2019 
12   
  • Propriétés de fermeture
  • Propriétés des langages hors-contexte (suite)
    • Algorithmes de décision pour LHC non-déterministes
  • Machines de Turing
    • Introduction

Travaux dirigés 10 (04 avril) : Révision – langages hors-contexte

 29 mars 2019 
13   
  • Machines de Turing (suite)
    • 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
  • Introduction aux problèmes indécidables

Travaux dirigés 11 (11 avril) : Machine de Turing et révision.

 05 avr. 2019 
14   

Examen final

 12 avr. 2019 
15   

Vendredi Saint

 19 avr. 2019 
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.

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