Travaux dirigés
TD n°1 [pdf][corrigé]
Un échauffement facile sur les automates finis et les langages rationnels puis quelques exercices sur les mots : commutativité, bords, et palindromes.
TD n°2 [pdf]
Des automates finis, des expressions rationnelles et des résiduels...
TD n°3 [pdf]
Quelques exercices un peu plus compliqués sur les langages rationnels.
TD n°4 [pdf][corrigé]
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°5 [pdf]
Un très joli problème sur les mots infinis dont on essaie de prédire certaines lettres avec un automate fini. C'était le dernier exercice du partiel d'automates en 2004.
TD n°6 [pdf]
Premiers exercices sur les grammaires algébriques (et un peu d'automates à pile aussi).
TD n°7 [pdf]
Des exercices simples sur les automates à piles et les langages algébriques.
TD n°8 [pdf]
Le lemme d'Ogden (une généralisation du lemme de l'étoile pour les langages algébriques).
TD n°9 [pdf]
Preuve d'équivalence entre les grammaires algébriques et les automates à pile non déterministes (avec un petit exercice pour montrer que toute grammaire peut être mise sous forme normale de Greibach).
TD n°10 [pdf]
Début des TD concernant la réécriture. Preuve de terminaison de certains systèmes de réécriture et lemme de Higman (dans toute suite infinie de mots sur un alphabet fini il existe un élément qui est un "sur-mot" d'un de ses prédécesseurs).
TD n°11 [pdf]
Lemme de Higman (encore), lemme de Newman (toute relation noethérienne localement confluente est confluente), W-confluence et propriété de Church-Rosser. Avec un exercice sur le jeu de Nim/Marienbad sur une grille infinie.
TD n°12 [pdf]
Un très joli énoncé de partiel écrit par Romain Kervarc pour le cours de réécriture en 2004-2005. Sur une thématique "grèce antique", il est constitué de 4 exercices indépendants :
- L'hydre de Lerne, où l'on décrit le combat d'Héraclès contre l'hydre, comme un système de réécriture sur les arbres, puis l'on montre que le combat termine toujours ;
- L'urne grecque, où l'on s'intéresse à la conflence d'un système de vote peu conventionnel ;
- Sacrifice à l'autel, où l'on considère un système de réécriture visant à répartir équitablement des animaux entre deux divinités ;
- Le jugement de Paris, où l'on étudie la confluence d'un système de réécriture sur les mots à 3 lettres.
Le sujet du partiel n'a pas été altéré (parce que la présentation était particulièrement travaillée).
TD n°13 [pdf]
Les ordinaux : définition, structure, premières propriétés, pour arriver finalement au fait que tout ensemble bien ordonné est isomorphe à un unique ordinal.
Partiel
Partiel de l'année 2006 - 2007 [pdf]
Le partiel correspond à tout le cours sur les langages rationnels, les automates finis et les expressions rationnelles. Il y a 5 exercices de difficulté variable.