Number of hours
- Lectures 24.0
- Projects -
- Tutorials 24.0
- Internship -
- Laboratory works -
- Written tests -
ECTS
ECTS 4.0
Goal(s)
Introduction to the formalisms and tools used for the definition and analysis of the syntax of formal languages. Application to programming languages.
Responsible(s)
Lionel RIEG
Content(s)
- Reminder about logic, quantifiers, and discrete mathematics
- Fixed point theorem on sets
- Inductive sets, reasoning by structural induction
- Formal languages
- Finite automata (deterministic and nondeterministic)
- Modeling with automata (protocol, control automaton)
- Automata transformation: elimination of epsilon transitions, determinization, minimization
- Regular expressions: equivalence with automata, RE beyond regular languages ??(see programming languages)
- Closure properties of regular languages, pumping lemma, nonregular languages
- Grammars and Chomsky hierarchy, general generation algorithm
- Context-free grammars: proofs on grammars, recognition algorithms (top-down and bottom-up), ambiguity and expression grammars, pumping lemma
- Structure and construction of a parser : lexical, syntactic (LL(1) and above) and semantic (attributed grammars) analysis
- Typing and properties guaranteed by a programming language
Recursive functions and call stack
Test
Evaluation : 20% of Projet (évaluation en continu et sur le rendu) and 80% of Examen Ecrit (2h)
Resit : Examen Ecrit (2h)
Allowed documents for the final exam: one double-sided handwritten A4 sheet
Calendar
The course exists in the following branches:
- Curriculum - Core curriculum - Semester 5
Additional Information
Course ID : 3MMTL
Course language(s): 
You can find this course among all other courses.