Descriptif
This course introduces different concepts in automata theory and formal languages, including formal proofs, deterministic and non-deterministic automata, regular expressions, regular languages, contextfree grammars and languages, and Turing machines.
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.
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade américainPour 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.
Pour 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)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
The star-height problem
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