Langages Formels

ENS Bretagne 1ere année -- 2007/2009

Me contacter pour obtenir les corrections.

2009

  • TD1 : Mots et Langages (télécharger le pdf ).
      Au programme :
    • Mots multiplicativement dépendants ;
    • Codes ;
    • Résiduels ;

  • TD2 : Langages Reconnaissables et Automates (télécharger le pdf ).
      Au programme :
    • Éxemples d'automates déterministes ;
    • Langages reconnaissables ;
    • Déterminisation ;
    • Caractérisation des langares rationnels.

  • TD3 : Langages Rationnels (télécharger le pdf ).
      Au programme :
    • Semi-linéarité ;
    • Non équivalence des lemmes d'itération ;
    • Langages rationnels ;
    • Le barman aveugle ;
    • Méthode de Thompson.

  • TD4 : Minimisation, Langages Rationnels, caractérisation de Nérode (télécharger le pdf ).
      Au programme :
    • Non-clotûre de Rat pour l'opération BORD ;
    • Minimisation ;
    • Caractérisation de Nérode ;
    • Stabilité de Rat par shuffle et substitution rationnelle.

  • TD5 : Carcatérisation logique de Rat, Automates séquentiels (télécharger le pdf ).
      Au programme :
    • Caractérisation logique de Rat ;
    • Automates séquentiels.

  • TD6 : Langages et Grammaires Algébriques (télécharger le pdf ).
      Au programme :
    • Calcul de langages engendrés ;
    • Recherche de grammaires.

  • TD7 : Forme normale de Chomsky et Lemme d'Ogden (télécharger le pdf ).
      Au programme :
    • Forme normale de Chomsky;
    • Lemme d'Ogden.

  • TD8 : Lemme de l'étoile, Lemme d'Ogden et centre d'un langage algébrique (télécharger le pdf ).
      Au programme :
    • Lemme de l'étoile;
    • Lemme d'Ogden;
    • Non-clôture par moitié;
    • Centre d'un langage algébrique.

  • TD9 : Langages algébriques et automates à pile (télécharger le pdf).
      Au programme :
    • Construction d'automates à pile;
    • Non-clôture par union dénombrable;
    • Centre d'un langage algébrique.

    2008

    • TD1 : Mots et Langages (télécharger le pdf)
        Au programme :
      • Mots multiplicativement dépendants ;
      • Codes ;
      • Résiduels ;
      • Mots de Lyndon.

    • TD2 : Langages Reconnaissables et Automates (télécharger le pdf)
        Au programme :
      • Éxemples d'automates déterministes ;
      • Langages reconnaissables ;
      • Déterminisation ;
      • Méthode de Thompson.

    • TD3 : Langages Rationnels (télécharger le pdf)
        Au programme :
      • Semi-linéarité ;
      • Non équivalence des lemmes d'itération ;
      • Langages rationnels.

    • TD4 : Minimisation, Langages Rationnels, caractérisation de Nérode (télécharger le pdf)
        Au programme :
      • Minimisation ;
      • Caractérisation de Nérode ;
      • Stabilité de Rat par shuffle et substitution rationnelle.

    • TD5 : Carcatérisation logique de Rat, Automates séquentiels (télécharger le pdf)
        Au programme :
      • Caractérisation logique de Rat ;
      • Automates séquentiels.

    • TD6 : Langages et Grammaires Algébriques (télécharger le pdf)
        Au programme :
      • Calcul de langages engendrés ;
      • Recherche de grammaires.

    • TD7 : Lemme de l'Étoile et Lemme d'Ogden (télécharger le pdf)
        Au programme :
      • Application du lemme de l'étoile pour les langages algébriques ;
      • Lemme d'Ogden.

    • TD8 : Langages Algébriques et Automates à Pile (télécharger le pdf)
        Au programme :
      • Construction d'automates à pile ;
      • Non-clôture par union dénombrable ;
      • Non-clôture par intersection, morphisme ;
      • Non-clôture par complémentaire.

    • TD9 : Propriétés des Langages Algébriques (télécharger le pdf)
        Au programme :
      • Non-clôture par complémentaire ;
      • Mélanges de langages ;
      • Langages algébriques sur un seul caractère.

    • TD10 : Mots Infinis (télécharger le pdf)
        Au programme :
      • Reconnaissance de Büchi et langages rationnels;
      • Prédiction des mots univers ;
      • Clôture par morphisme inverse.

    • TD11 : Automates de Büchi, Muller et Rabin (télécharger le pdf)
        Au programme :
      • Déterminisation des Büchi en Rabin ;
      • Algorithme de Safra ;
      • Automates de Muller à table entièrement définie ;
      • Décidabilité du déterminisme et autres propriétés ;
      • Jeux Pi2.

      2007

      • TD1 : Mots et Langages (télécharger le pdf)
          Au programme :
        • Mots multiplicativement dépendants ;
        • Codes ;
        • Résiduels ;
        • Mots de Lyndon.

      • TD2 : Langages Reconnaissables et Automates (télécharger le pdf)
          Au programme :
        • Éxemples d'automates déterministes ;
        • Langages reconnaissables ;
        • Déterminisation ;
        • Méthode de Thompson.

      • TD3 : Langages Rationnels (télécharger le pdf)
          Au programme :
        • Semi-linéarité ;
        • Non équivalence des lemmes d'itération ;
        • Langages rationnels ;
        • Le barman aveugle.

      • TD4 : Minimisation, Langages Rationnels, caractérisation logique de Rat (télécharger le pdf)
          Au programme :
        • Minimisation ;
        • Caractérisation de Nérode ;
        • Caractérisation logique de Rat.

      • TD5 : Langages Algébriques et Automates Séquentiels (télécharger le pdf)
          Au programme :
        • Langages engendrés par des grammaires ;
        • Grammaires engendrant des langages ;
        • Automates séquentiels.

      • TD6 : Lemme de l'Étoile et Lemme d'Ogden (télécharger le pdf)
          Au programme :
        • Application du lemme de l'étoile pour les langages algébriques ;
        • Lemme d'Ogden ;
        • Langage moitié.

      • TD7 : Langages Algébriques et Automates à Pile (télécharger le pdf)
          Au programme :
        • Construction d'automates à pile ;
        • Non-clôture par union dénombrable ;
        • Non-clôture par complémentaire ;
        • Langages algébriques sur un seul caractère.

      • TD8 : Langages Algébriques et Mots Infinis (télécharger le pdf)
          Au programme :
        • Mélange de langages ;
        • Prédiction des mots univers ;
        • Clôture par morphisme inverse.

      • TD9 : Automates de Büchi, Muller et Rabin (télécharger le pdf)
          Au programme :
        • Déterminisation des Büchi en Rabin ;
        • Automates de Muller à table entièrement définie.

      • TD10 : Décidabilité et jeux Pi2 (télécharger le pdf)
          Au programme :
        • Décidabilité du déterminisme ;
        • Jeux Pi2 ;
        • Calcul de rang.