Master Sciences, Technologies, Santé

Objectifs

Basic notions of Formal Language Theory in view of the applications to compilation.

Programme

Regular expressions, finite automata, Kleene's Theorem, translations between automata and regular expressions.
Context-free grammars, derivation trees, ambiguity, grammar for arithmetical expressions, constructions and transformations of grammars.
Top-down parsing for simple deterministic (particular LL(1)) grammars.
Languages that are not context-free , or context-free but not regular.
Intersection of a context-free and a regular language
Proofs of properties of the words of a context-free language.

Compétences acquises

Basic constructions of grammars, automata and regular expressions.
Proofs and definitions by induction on the length of words or the structure of a regular expression.

Répartition des enseignements

Semaines	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	Durées
CM																03h00

Volume des enseignements

	Heures en présentiel
Cours Magistraux	20
Travaux Dirigés	40
Travaux Pratiques	0
Cours intégrés	0
TD sur machine	0
Accompagnement	0

Bibliographie

S. Crespi-Reghizzi, Formal languages and Compilation, Springer 2009.

Mode d'évaluation

Epreuves 1ère session

Type d'évaluation

Détails éventuels

Durées

Coefficients

Examen écrit terminal

03h00

2/3

Contrôle Continu (CC)

00h00

1/3

Epreuves 2ème session

Type d'évaluation

Détails éventuels

Durées

Coefficients

Examen écrit terminal

03h00

2/3

Contrôle Continu (CC)

report session 1

00h00

1/3

Note session 2 = CoeffEx2 * Ex2 + coeffCC * max(Ex2,CC)
UE du parcours GL-Vietnam.

Public concerné

Formation initiale

Forme d’enseignement

Enseignement présentiel

Lieu d'enseignement

• Autres

Langue d'enseignement

Anglais

Responsable(s)