Travaux dirigés
TD n°1 [pdf]
Travail sur les propriétés élémentaires des mots : les palindromes, les codes, les résiduels, les bords, etc.
TD n°2 [pdf]
Quelques exercices simples sur les automates finis et les langages rationnels et un exercice sur les mots de Lyndon. Un corrigé de l'exercice sur les mots de Lyndon (correspondant au TD d'automates de l'année précédente) est disponible [pdf].
TD n°3 [pdf]
Des exercices sur les automates finis et les langages rationnels.
TD n°4 [pdf]
Quelques exercices choisis du partiel de l'année précédente (dont un problème de "prédiction" des mots infinis non univers par des automates finis).
Pour une raison inconnue les TD 5, 6, 7 et 8 ont disparu...
TD n°9 [pdf]
Quelques exercices sur les langages de mots infinis, le théorème de Büchi et les limites de langages.
TD n°10 [pdf]
Des exercices élémentaires sur les machines de Turing (quelques exemples, accélération linéaire, réduction de l'alphabet et de l'espace de travail, etc.).
TD n°11 [pdf]
Un problème sur les machines à compteurs où l'on prouve l'universalité au sens de Turing. Deux autres exercices sur les machines de Turing.
TD n°12 [pdf]
Indécidabilité du problème de correspondance de Post et quelques questions concernant les ensembles récursivement énumérables et les ensembles récursifs.
Partiel
Partiel de l'année 2005-2006 [pdf]
Le partiel ne porte que sur les langages rationnels et les automates finis. Il comporte 6 exercices indépendants dont un problème sur les automates "boustrophédons" capables de se déplacer sur le mot en entrée dans les deux sens.