v2.6.4 (3793)

Cours scientifique - CSE206 : Introduction to Formal Languages

Domaine > Informatique.

Descriptif

This course introduces different concepts in automata theory and formal languages, including deterministic and non-deterministic finite automata, regular expressions, context-free grammars, (weak) pushdown automata, and, through the example of a minimalistic programming language, the relation between unconstrained grammars and computability.

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 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.

    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)

      La note obtenue rentre dans le calcul de votre GPA.

      Programme détaillé

      • Grammars and Formal Languages
        1. Operations on languages
        2. Rewriting
        3. Grammars
      • Regular Languages and Finite State Automata
        1. Finite State Automata
        2. Regular languages vs Finite Automata
        3. Pumping lemma
        4. Deciding emptiness and finiteness
      • Regular Expressions
        1. Syntax
        2. Interpretation
      • Kleene theorem
        1. The Brzozowski - McCluskey state elimination procedure
      • Star-height problem (a glimpse at)
      • Determinism
        1. Powerset automaton
        2. Completion
        3. Stability under complement
      • Minimization
        1. Myhill - Nerode theorem
        2. Moore algorithm
        3. Brzozowski's algorithm
      • Lexing (a glimpse at)
      • Context-Free Grammars
        1. Chomsky normal form
        2. Pushdown automata (weak)
        3. Pumping lemma
        4. Eliminating left-recursiveness
      • The BitFlip language
        1. Syntax and Semantics
        2. An (unconstrained) grammar based interpreter

      Mots clés

      grammar, automata, regular expression, context-free, computability
      Veuillez patienter