| Cours 1 : lundi 7 septembre 2015 à 16h |
Transparents pour les 3 premiers cours
Représenter des objets infinis avec des objets finisIntroduction : des exemples et objectifs du moduleMots. Concaténation de mots. Monoïde. Morphisme de monoïdes. Langages. Opérations : union, intersection, concaténation, itérations. Expressions rationnelles : syntaxe et sémantique. Langage rationnel. Logique monadique du second ordre (MSO) : exemples, syntaxe et sémantique. |
| TD 1 : vendredi 11 septembre 2015 à 14h | Mots et langages |
| Cours 2 : lundi 14 septembre 2015 à 16h |
Automates : théorème de Kleene et conséquencesAutomate non-déterministe avec epsilon-transitions. Automate non-déterministe sans epislon-transitions. Automate déterministe. Exécution. Langage accepté. Langage reconnaissable.Théorème de Kleene (1er sens : expression régulière vers automate, construction de Thomson) Outil : des expressions rationnelles aux automates Outil : de MSO aux automates Théorème de Kleene (2e sens : automate vers expression régulière, Brzozowski-McCluskey, automates généralisés) Lemme de pompage Stabilité par intersection : produit d'automates Démonstration de la borne supérieure exponentielle (et polynomiale pour une représentation en DAG) de la taille de l'expression rationnelle obtenu par l'algorithme de Brzozowski-McCluskey Démonstration que langages définis par MSO sont exactement les langages reconnaissables |
| TD 2 : vendredi 18 septembre 2015 à 14h | Automates |
| Cours 3 : lundi 21 septembre 2015 à 16h |
Stabilité par complémentaire : déterminisation Panorama des représentations (expressions rationnelles, automates ,MSO) Automate minimalAutomate minimal. Automate quotient. Automate des résiduels. Caractérisation d'un rationnel avec nombre fini de résiduels. Unicité de l'automate minimal. Algorithme de minimisation. |
| TD 3 : vendredi 25 septembre 2015 à 14h | Minimisation |
| Cours 4 : lundi 28 septembre 2015 à 16h |
Correction de l'algorithme de Moore Implémentation de l'algorithme de Moore. Caractérisation par morphisme. Stabilité par morphisme et morphisme inverse. Monoïde syntaxique. Théorème de Schützenberger : si L est rationnel, alors L est sans étoile ssi son monoïde syntaxique est apériodique. (admis) Pour aller plus loinThéorème de McNaughton : si L est rationnel non vide, L est sans étoile ssi il est définissable par une formule du premier ordre.Article qui donne une vue d'ensemble sur automates et premier ordre Application des automates : Arithmétique de Presbuger. Description de la transformation formule => automate Application des automates : analyse lexicale. Description des algorithmes. Démonstration |
| TD 4 : vendredi 2 octobre 2015 à 14h | propriétés de clôtures des reconnaissables/rationnels |
| Cours 5 : lundi 5 octobre 2015 à 16h |
Transparents sur les langages algébriques
Langages algébriquesIntroduction avec deux exemples : {a^ncb^n} (pour montrer deux non-terminaux) et le langage de Lukasiewicz (pour montrer plusieurs dérivations mais un arbre de dérivation) Définitions formelles des grammaires hors contexte, dérivations, langage engendré. Lemme fondamental (découpage de dérivations). Arbre de dérivation. Exemples de langages algébriques : Langage de Dyck, langages de Lukacieviez (notations préfixes), notations postfixesConcevoir des grammaires algébriquesClotûre par concaténation, union, étoile. Pour un langage rationnel : automate fini vers grammaires linéaires à gauche Ambiguité. Battre l'ambiguité. Exemple des expressions infixes.Au delà des algébriquesLemme de pompage de Bar-Hillel, Perles et Shamir{a^nb^nc^n} n'est pas algébrique. (PAS FAIT, FAIT EN TD)
Pas de clotûre par intersection, ni par complémentaire. (PAS FAIT, COURS D'APRES)
Bonus : quelques mots sur la hierarchie de Chomsky : grammaires avec contextes et grammaires générales (PAS FAIT, REPORTE A LA FIN)
|
| TD 5 : vendredi 9 octobre 2015 à 14h | Grammaire, ambiguïté |
| Cours 6 : lundi 12 octobre 2015 à 16h |
Nettoyer une grammaireSupprimer les règles non accessibles Supprimer les règles non productives DémonstrationMise en forme normale de ChomskyDéfinition Algorithme DémonstrationAlgorithme CYKPrincipe de programmation dynamique. Algorithme Démonstration Discussion informelle autour de l'intérêt de la mise en forme normale de ChomskyVers le théorème de SchützenbergerPremier pas : stabilité par intersection avec un rationnel, stabilité par morphisme. Théorème de Schützenberger |
| TD 6 : vendredi 16 octobre 2015 à 14h | Lemme d'itérations |
| Cours 7 : lundi 19 octobre 2015 à 16h |
Automates à pileTransparents du cours Exemples pour {a^nb^n}les palindrômes, {a^ib^jc^k, i diff j ou i diff k}
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.Définition formelle d'un automate à pile déterministe. Langages déterministes. Clotûre par complémentaire des langages déterministes. (PARTIELLEMENT)
Démonstration de la clotûre des langages déterministes par complémentaire
Pas de clotûre par intersection/union/concaténation/étoile |
| TD 7 : vendredi 23 octobre 2015 à 14h | Automates à pile |
| VACANCES | |
| Cours 8 : lundi 2 novembre 2015 |
Analyse syntaxiqueAnalyse descendante LL(1). Ensemble premier et suivant. Calcul des premiers et suivants. Grammaire LL(1).Analyse ascendante LR(0). Automates des items LR(0) (exemple). Conflits. Grammaire LR(0). Idée de l'automate à pile déterministe. Outil pédagogique pour les analyses syntaxiques |
| TD 8 : vendredi 6 novembre 2015 à 14h | Automates à pile (suite) |
| Cours 9 : lundi 9 novembre 2015, 16h | Machine de Turing |
| TD 9 : vendredi 13 novembre 2015 à 14h | Simulateur de machine de Turing déterministe |
| Cours 10 : lundi 16 novembre 2015, 16h | |
| TD 10 : vendredi 20 novembre 2015, 14h | |
| Cours 11 : lundi 23 novembre 2015, 16h | |
| TD 11 : vendredi 27 novembre 2015, 14h | |
| Cours 12 : lundi 30 novembre 2015, 16h | |
| TD 12 : vendredi 4 décembre 2015, 14h |