étendre l'analyse syntaxiques des langages, des langages réguliers aux langages algébriqsues (aka hors-contextes)
étudier les propriétés de clôtures et de non-clotûres des langages algébriques, en analogie avec celles des langages réguliers
appliquer les méthodes discrètes (récurrence, induction structurelle, raisonnement par l'absurde…) et des règles de logique élémentaire (implication, quantification, négation…) sur des problèmes de théorie des langages
préparer l'analyse sémantique des langages, via les notions de grammaires, d'arbres de dérivation, d'ambiguité
entrevoir les problèmes algorithmiques sur les langages algébriques (notamment, indécidabilité (non-démontrée) de certains problèmes)
Plan du cours
Intro & rappels sur les langages réguliers
Définitions grammaires, dérivations
Formes normale de Chomsky
Lemme de pompage algébrique
Automates à pile
non-déterministes
déterministes
Propriétés de clôture/non-clôture de la classe des langages algébriques
Hierarchie de Chomsky
Description des TP
A remplir
Connaissances requises
Langages réguliers
automates finis
déterminisme/non-déterminisme
opérations (union, intersection, complément, concaténation, itération (aka étoile), …) sur les automates
produite d'automates
déterminisation
minimisation
lemme de pompage régulier (aka lemme d'itération régulier, aka lemme de l'étoile)
