TD n° 1 [ps][pdf]
Un échauffement facile sur les automates finis et les
langages
rationnels puis quelques exercices sur les mots :
commutativité,
bords, et palindromes. Sylvain a très gentiment
écrit un
corrigé : [ps][pdf]
TD n° 2 [ps][pdf]
Des automates finis, des expressions rationnelles et des
résiduels...
TD n° 3 [ps][pdf]
Quelques exercices un peu plus compliqués sur les langages
rationnels.
TD n° 4 [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.
Avec un corrigé pour rassurer les
élèves juste avant le partiel : [ps][pdf]
TD n° 5 [ps][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 [ps][pdf]
Premiers exercices sur les grammaires algébriques (et un peu d'automates à pile aussi).
TD n° 7 [ps][pdf]
Des exercices simples sur les automates à piles et les langages algébriques.
TD n° 8 [ps][pdf]
Le lemme d'Ogden (une généralisation du lemme de l'étoile pour les langages algébriques).
TD n° 9 [ps][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 [ps][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 [ps][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 [ps][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). Un corrigé est disponible sur la page de Romain.
TD n° 13 [ps][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.
|