v2.11.0 (5648)

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

    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é

      • 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