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.
Diplôme(s) concerné(s)
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 20Littérale/grade américainPour 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)- Crédits ECTS acquis : 3 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
- Grammars and Formal Languages
- Operations on languages
- Rewriting
- Grammars
- Regular Languages and Finite State Automata
- Finite State Automata
- Regular languages vs Finite Automata
- Pumping lemma
- Deciding emptiness and finiteness
- Regular Expressions
- Syntax
- Interpretation
- Kleene theorem
- The Brzozowski - McCluskey state elimination procedure
- Star-height problem (a glimpse at)
- Determinism
- Powerset automaton
- Completion
- Stability under complement
- Minimization
- Myhill - Nerode theorem
- Moore algorithm
- Brzozowski's algorithm
- Lexing (a glimpse at)
- Context-Free Grammars
- Chomsky normal form
- Pushdown automata (weak)
- Pumping lemma
- Eliminating left-recursiveness
- The BitFlip language
- Syntax and Semantics
- An (unconstrained) grammar based interpreter