http://perso.ens-lyon.fr/victor.poupet
e-mail: victor [point] poupet [at] ens-lyon [point] fr
home

ENSEIGNEMENT : Automates et langages formels (1er semestre 2004 - 2005)

Cours de Marianne Delorme en L3 à l'ENS Lyon.
Les TD ont été écrits avec Stéphane Le Roux, également chargé de TD.

TRAVAUX DIRIGES


TD n° 1 [ps][pdf]

Travail sur les propriétés élémentaires des mots : les palindromes, les codes, les résiduels, les bords, etc.

TD n° 2 [ps][pdf]
Encore des mots : conjuguaison, commutation et mots de Lyndon. Un corrigé de l'exercice sur les mots de Lyndon est disponible [ps][pdf].

TD n° 3 [ps][pdf]
Premiers exercices sur les automates finis et les langages rationnels.

TD n° 4 [ps][pdf]
Un problème sur les langages rationnels qui généralise quelques résultats obtenus dans le dernier exercice du TD précédent : on caractérise les fonctions f : N -> N telles que pour tout langage rationnel L, le langage des mots u tels qu'il existe un mot v de longueur f(|u|) tel que uv appartienne à L est rationnel.

TD n° 5 [ps][pdf]
Un problème sur les langages rationnels qui généralise quelques résultats obtenus dans le dernier exercice du TD précédent : on caractérise les fonctions f : N -> N telles que pour tout langage rationnel L, le langage des mots u tels qu'il existe un mot v de longueur f(|u|) tel que uv appartienne à L est rationnel.

TD n° 6 [ps][pdf]
Un problème tiré d'un article de Marvin Minsky et Seymour Papert "Unrecognizable Sets of Numbers" qui permet de montrer que certains ensembles d'entiers (comme les nombres premiers par exemple) ne sont pas des langages rationnels quand on considère leurs écritures en base 2.

TD n° 7 [ps][pdf]
Premiers exercices sur les grammaires algébriques et contextuelles.

TD n° 8 [ps][pdf]
Preuve du lemme d'Ogden, qui est une version améliorée du lemme de l'étoile pour les langages algébriques.

TD n° 9 [ps][pdf]
Définition des automates à pile en TD, et preuve des premières propriétés (équivalence des grammaires algébriques et des automates à pile non déterministes et inclusion stricte des langages reconnus par automates à pile déterministes).

TD n° 10 [ps][pdf]
Des exercices sur les automates à pile et les grammaires algébriques.

TD n° 11 [ps][pdf]
Encore des exercices sur les langages algébriques, les automates à pile et les grammaires...

TD n° 12 [ps][pdf]
Dernier TD. Travail sur les langages de mots infinis et les automates de Büchi.

PARTIEL

Partiel de l'année 2004 - 2005 [ps][pdf]

Le partiel ne porte que sur les langages rationnels. Il comporte 6 exercices dont un "mini-problème" sur les mots infinis et un type particulier d'automates (définis dans l'énoncé).

draconis infernvs II - deligaris
image : Big Blue Sky - RozeChan