FOND1 - Fondements de l'informatique 
Formal languages

Ecole normale supérieure de Rennes - Département informatique et télécommunications - Année 2016/2017


Intervenants

Evaluation




Cours 1 par François Schwarzentruber à Beaulieu : jeudi 8 septembre 2016 à 14h

Motivation et présentation du cours

Représentation par des mots

Mots. Concaténation de mots.
Langages. Opérations : union, intersection, concaténation, itérations.

Partie 1. Langages rationnels

Expressions rationnelles

Expressions rationnelles : syntaxe et sémantique. Discussion sur la représentation : arbre syntaxique et graphe acyclique. Langage rationnel.

Automates finis

Automate non-déterministe avec epsilon-transitions. Exécution. Langage accepté. Langage reconnaissable.

Théorème de Kleene

Construction de Thompson. Algorithme de Brzozowski-McCluskey (juste un exemple). 		Fiche
TD 1 par Gilles Lesventes à Beaulieu : vendredi 9 septembre 2015 à 14h Comprendre le théorème de Kleene. La construction de Thompson et l'algorithme de Brzozowski-McCluskey. Feuille de TD
Cours 2 par François Schwarzentruber à Beaulieu : jeudi 15 septembre 2016 à 14h Démonstration de la correction de l'algorithme de Brzozowski-McCluskey
Lemme de pompage

Automates déterministes complets

Correction de la déterminisation
Intersection, union : produit d'automates. Stabilité par complémentaire.

Type abstrait "langage rationnel"

Opérations sur les langages rationnels. Application : arithmétique de Presburger. 		Fiche
TD 2 par Gilles Lesventes à Beaulieu : lundi 19 septembre 2016 à 14h Modélisation d'un système par un automate. D'autres propriétés de clotûre. Pratiquer le lemme de pompage. Feuille de TD
Cours 3 par François Schwarzentruber à Beaulieu : jeudi 22 septembre 2016 à 14h

Automate minimal

Unicité de l'automate minimal :
  • Quotient d'un automate.
  • Quotient d'un automate minimal = lui-même.
  • Automate des résiduels. Caractérisation d'un rationnel avec nombre fini de résiduels.
  • Un quotient est l'automate des résiduels.
Algorithme de Moore. Correction. Implémentation de l'algorithme de Moore (pas fait en cours).
 Fiche
TDmaths 3 par Gilles Lesventes à Ker Lann : lundi 26 septembre 2016 à 8h Minimisation Feuille de TD
TDinfo 3 par Gilles Lesventes à Beaulieu : jeudi 29 septembre 2016 à 8h Minimisation Feuille de TD
Cours 4 par François Schwarzentruber à Beaulieu : jeudi 29 septembre 2016 à 14h
Salle de 36 places

Partie 1. Langages algébriques

Grammaires algébriques

Définitions formelles des grammaires hors contexte, dérivations, langage engendré. Arbre de dérivation.
Illustration des notions avec des exemples.
Caractérisation du langage de Lukacieviez (notations préfixes)
Stabilité par concaténation, union et étoile de Kleene. Ambiguïté. Langage intrinséquent ambigü
Lemme de pompage de Bar-Hillel, Perles et Shamir
Non-stabilité par intersection et complémentaire. 		Fiche
TDinfo 4 par Gilles Lesventes à Beaulieu : vendredi 30 septembre 2016 à 14h
Salle de 18 places		 Grammaires, ambiguïté Feuille de TD
TDmaths 4 par Gilles Lesventes à Ker Lann : lundi 3 octobre 2016 à 16h
Salle de 18 places		 Grammaires, ambiguïté Feuille de TD
Cours 5 par François Schwarzentruber à Beaulieu : jeudi 6 octobre 2016 à 14h
Salle de 36 places

Problème du mot pour les langages algébriques

Nettoyage une grammaire : supprimer les règles non accessibles, supprimer les règles non productives.
Mise en forme normale de Chomsky.
Démonstration
Algorithme CYK
Démonstration

Automates à pile

Exemple pour {a^nb^n} 		Fiche
TDinfo 5 par Gilles Lesventes à Beaulieu : vendredi 7 octobre 2016 à 14h
Salle de 18 places		 Lemme d'itérations Feuille de TD
TDmaths 5 par Gilles Lesventes à Ker Lann : lundi 10 octobre 2016 à 16h
Salle de 18 places		 Lemme d'itérations Feuille de TD
Cours 6 par François Schwarzentruber à Beaulieu : jeudi 13 octobre 2016 à 16h
Salle de 36 places

Automates à pile (suite)

Définition formelle d'un automate à pile non-déterministe. Configuration. Transitions. Langage reconnu par état final.
Equivalence entre langage algébrique et automates à pile non-déterministes.
L'intersection d'un algébrique avec un rationnel est algébrique (produit d'un automate à pile et d'un automate fini)
Automate à pile déterministe.
Langages déterministes.
Idée de la démonstration de la clotûre par complémentaire des langages déterministes.
Pas de clotûre par intersection/union/concaténation/étoile 		Fiche
TDinfo 6 par Gilles Lesventes à Beaulieu : vendredi 14 octobre 2016 de 14h à 16h
Salle de 18 places		 Automates à pile Feuille de TD
TDmaths 6 par Gilles Lesventes à Ker Lann : lundi 17 octobre 2016 de 16h à 18h
Salle de 18 places		 Automates à pile Feuille de TD
VACANCES du 20 octobre au 1er novembre 2016
Cours 7 par Gilles Lesventes à Beaulieu : jeudi 3 novembre 2016 de 14h de 16h à 18h
Salle de 36 places
TDinfo 7 par David Cachera à Beaulieu : vendredi 4 novembre 2016 de 14h de 16h à 18h
Salle de 18 places
TDmaths 7 par Gilles Lesventes à Beaulieu : vendredi 4 novembre 2016 de 14h à 16h
Salle de 18 places
Cours 8 par Gilles Lesventes à Beaulieu : jeudi 10 novembre 2016 de 14h à 16h
Salle de 36 places
TDinfo 8 par David Cachera à Ker Lann : lundi 14 novembre 2016 de 16h à 18h
Salle de 18 places
TDmaths 8 par Gilles Lesventes à Ker Lann : lundi 14 novembre 2016 de 16h à 18h
Salle de 18 places
Cours 9 par Gilles Lesventes à Beaulieu : jeudi 17 novembre 2016 de 14h à 16h
Salle de 36 places
TDinfo 9 par David Cachera à Beaulieu : vendredi 18 novembre 2016 de 14h à 16h
Salle de 18 places
TDmaths 9 par Gilles Lesventes à Beaulieu : vendredi 18 novembre 2016 de 14h à 16h
Salle de 18 places
Cours 10 par Gilles Lesventes à Beaulieu : jeudi 24 novembre 2016 de 14h à 16h
Salle de 36 places
TDinfo 10 par David Cachera à Beaulieu : vendredi 25 novembre 2016 de 14h à 16h
Salle de 18 places
TDmaths 10 par Gilles Lesventes à Beaulieu : vendredi 25 novembre 2016 de 14h à 16h
Salle de 18 places
Examen à Beaulieu : mercredi 14 décembre de 10h15 à 12h15
I59		 Examen sur table (tous documents autorisés)


References