Descriptif
We introduce different concepts from automata theory and formal languages, including grammars,
deterministic and non-deterministic automata, regular expressions and languages, and
context-free languages. We approach computability through the a very simple model:
the BitFlip language, whose abstract machine is simulated by an unrestricted grammar.
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
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)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