Descriptif
The course introduces different concepts related to formal languages, including regular/context-free/unrestricted grammars, finite/pushdown automata, regular expressions/languages.
These concepts are motivated by concrete examples (word completion, programming language design); in particular we explain how unrestricted grammars can be used as models of computation.
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.
24.5 heures en présentiel (7 blocs ou créneaux)
20 heures de travail personnel estimé pour l’étudiant.
Diplôme(s) concerné(s)
Parcours de rattachement
Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique
Aucun
Pour les étudiants du diplôme Programmes d'échange internationaux
Aucun
Format des notes
Numérique sur 20Littérale/grade américainPour les étudiants du diplôme Programmes d'échange internationaux
Vos modalités d'acquisition :
One final exam plus 3 tiny tests at the beginning of tutorials 4, 5, and 6.
The final exam is made of small exercices covering the whole content of the course.
The results of the tiny tests are used as an adjustment variable.
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
Vos modalités d'acquisition :
One final exam plus 3 tiny tests at the beginning of tutorials 4, 5, and 6.
The final exam is made of small exercices covering the whole content of the course.
The results of the tiny tests are used as an adjustment variable.
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é
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
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