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