v2.11.0 (5380)

Cours scientifique - CSE206 : Introduction to Formal Languages

Domaine > Informatique.

Descriptif

We introduce different concepts from automata theory and formal languages, including grammars, 
deterministic and non-deterministic automata, regular expressions and languages, and
context-free languages. We approach computability through the a very simple model:
the BitFlip language, whose abstract machine is simulated by an unrestricted grammar.

 

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.

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

Vous devez avoir validé l'équation suivante : UE CSE203

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme Echanges PEI

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

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

    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.

      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