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.
|