Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Fondements de l'informatique
Thèmes :
Languages, Automates & Calculabilité
,
Logique & Preuve
–
Cursus :
ENS-Lyon - L3
2006 - 2007, Semestre 1
TDs
Sylvain Périfel
,
Victor Poupet
description des TDs et du partiel
TD1 : automates finis et mots
TD1 : correction
TD2 : automates finis
TD3 : langages rationnels
TD3 : exercice sur la caractérisation des fonctions f telles que f(L) est rationnel pour tout langage rationnel L
TD4 : un résultat de Minsky et Papert
TD4 : correction
TD5 : mots prédictibles et mots univers
TD6 : grammaires algébriques et automates à pile
TD7 : automates à pile et langages algébriques
TD8 : lemme d'Ogden (généralisation du lemme de l'étoile pour les langages algébriques)
TD9 : équivalence grammaires algébriques / automates à piles
TD10 : terminaison de systèmes de réécriture, lemme de König, lemme de Higman
TD11 : lemme de Higman (fin), lemme de Newman, jeu de Nim
TD12 : partiel 2004
TD13 : ordinaux