v2.11.0 (5725)

Cours scientifiques - CSC_2S006_EP : Introduction to Formal Languages

Domaine > Informatique.

Descriptif

This course introduces different concepts in automata theory and formal languages, including formal proofs, deterministic and non-deterministic automata, regular expressions, regular languages, contextfree grammars and languages, and Turing machines.

 

Objectifs pédagogiques

Students are expected to acquire, at least, an intuitive understanding of the concepts so that they can easily deal with standard examples.

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vos modalités d'acquisition :

One final exam plus 3 tiny tests at the beginning of tutorials 4, 5, and 6.

The final exam is made of small exercices covering the whole content of the course.

The results of the tiny tests are used as an adjustment variable.

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)
    L'UE est acquise si Note finale >= 10
    • Crédits ECTS acquis : 3 ECTS

    La note obtenue rentre dans le calcul de votre GPA.

    Pour les étudiants du diplôme Programmes d'échange internationaux

    Vos modalités d'acquisition :

    One final exam plus 3 tiny tests at the beginning of tutorials 4, 5, and 6.

    The final exam is made of small exercices covering the whole content of the course.

    The results of the tiny tests are used as an adjustment variable.

    Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)

      Programme détaillé

      1) 
      Grammars and Formal Languages : 
        Operations on languages, 
        Rewriting, 
        Grammars, 
        Two important classes of grammars
      
      2) 
      Regular Languages and Finite State Automata : 
        Finite state automaton, 
        Regular languages vs Finite Automata, 
        The pumping lemma, 
        Deciding emptiness and finiteness
      
      3) 
      Regular expressions : 
        The language of Regular expressions, 
        Interpretation of Regular expressions, 
        The Kleene theorem Proof of the Kleene theorem
          From Regular expressions to Automata
          
      4) 
      Proof of the Kleene theorem (continued) :
         Generalised finite automata, 
         The Brzozowski - McCluskey state elimination procedure
      The star-height problem
      Deterministic finite automata :
         The powerset construction, 
         Completion, 
         Adding the complement operator to regular expressions
         
      5) 
      Smallest deterministic finite automata :
        The Myhill - Nerode theorem, 
        The Moore algorithm, 
        The Brzozowski's algorithm
      
      Lexing
      
      6)
      Context-Free languages:
        Basic transformations, 
        Chomsky normal forms, 
        Weak pushdown automata, 
        The pumping lemma, 
        Eliminating left-recursiveness
      
      7)
      The BitFlip language :
        Syntax and Semantics
      
      Interpretation as an unconstrained grammar :
        Rules and Facts
      

      Mots clés

      Formal Languages, Regular Expressions, Context-Free Languages, Myhill - Nerode, Kleene, Brzozowski - McCluskey
      Veuillez patienter