Théorie des langages
Manipuler alphabets, mots et langages formels ; construire des automates, prouver la non-régularité, et remonter jusqu'à l'analyseur d'un compilateur.
Commencer : Mots et langages- C1Non commencé
Fondements
2 leçons · 10 hObjectif. Manier les mots et les langages comme des objets mathématiques, et se doter des outils de preuve — induction, récurrence — dont dépend tout le cours.
- Mots et langagesVous êtes iciAlphabet, mot, longueur, mot vide ; concaténation, préfixe, suffixe, facteur ; le langage comme ensemble de mots ; union, concaténation, étoile de Kleene ; dénombrer les mots.5 h · en cours
- Rappels mathématiques utilesEnsembles et relations, induction structurelle, récurrence sur la longueur d'un mot, et la notion de fonction de transition dont dépendent les automates.5 h · non commencée
- C2Non commencé
Langages réguliers
4 leçons · 20 hObjectif. Le cœur du cours : automates, expressions régulières et le théorème de Kleene qui les relie, jusqu'à savoir prouver qu'un langage n'est pas régulier.
- Automates finis déterministesÉtats, transitions, état initial, états acceptants ; exécution et acceptation d'un mot ; construire un AFD pour un langage donné ; automate complet.5 h · non commencée
- Automates non déterministesAFN et ε-transitions ; déterminisation par construction des sous-ensembles ; équivalence AFD/AFN — le premier point qui coince.5 h · non commencée
- Expressions régulièresSyntaxe et sémantique ; théorème de Kleene, expressions régulières ↔ automates finis ; construction de Thompson et élimination d'états.5 h · non commencée
- Propriétés et limitesMinimisation d'automate, propriétés de clôture, lemme de pompage et preuves de non-régularité — le cas a^n b^n, le second point qui coince.5 h · non commencée
- C3Non commencé
Langages algébriques
2 leçons · 14 hObjectif. Monter d'un cran dans la hiérarchie : grammaires hors contexte et automates à pile, et la limite que le lemme de pompage algébrique leur impose.
- Grammaires hors contexteGrammaire, dérivation, arbre de dérivation ; langage engendré ; ambiguïté ; forme normale de Chomsky ; la hiérarchie de Chomsky en survol.7 h · non commencée
- Automates à pilePile et transitions ; acceptation par pile vide ou par état final ; équivalence avec les grammaires hors contexte ; lemme de pompage algébrique.7 h · non commencée
- C4Non commencé
Applications
1 leçon · 6 hObjectif. Voir la théorie devenir un outil : l'analyse lexicale et syntaxique d'un compilateur, et les outils qui l'automatisent.