Théorie des langages

Composante	Télécom Physique Strasbourg (TPS)
Langue(s) d'enseignement	Français
Heures d'enseignement	CM : 19,25 h TD : 22,75 h
Ouvert aux étudiants d'autres disciplines
Ouvert aux étudiants en échange
Code Apogée	EP0F1M04

Compétences requises

Connaissances mathématiques de base

Basic mathematical knowledge

Compétences visées

Ce cours a pour but de présenter la notion de langage formel et plus particulièrement les deux premières classes dans la hiérarchie de Chomski : les langages rationnels et les langages algébriques. Syntaxiquement, les premiers correspondent grosso modo aux expressions régulières et les seconds aux langages de programmation.

Ce cours est un cours fondamental apportant des connaissances importantes pour bien comprendre la notion de langage de programmation. En dehors des compétences techniques de simplification et de déterminisation d'automates et de grammaires, prérequis au cours de compilation, l'étudiant aura acquis des compétence en abstraction de problèmes et raisonnement formel.

This course aims to present the notion of formal language and more particularly the first two classes in the hierarchy of Chomski: rational languages and algebraic languages. Syntactically, the first roughly correspond to regular expressions and the second to programming languages.

This course is a fundamental course providing important knowledge to understand the concept of programming language. Apart from the technical skills of simplification and determinization of automata and grammars, prerequisites during compilation, the student will have acquired competence in problem abstraction and formal reasoning.

Syllabus

Notions de langages formels. Expressions rationnelles. Automates d'états finis (déterministes et non déterministes). Déterminisation et minimisation d'automates. Propriétés de stabilité de la classe des langages rationnels. Lemme de l'étoile. Grammaires algébriques. Automates à pile. Propriétés de stabilité de la classe des langages algébriques. Lemme de la double étoile. Équivalences automates-grammaires.

Notions of formal languages. Rational expressions. Finite state automata (deterministic and non-deterministic). Determination and minimization of automata. Stability properties of the class of rational languages. Lemma of the star. Algebraic grammars. Battery powered automatons. Stability properties of the class of algebraic languages. Lemma of the double star. Automata-grammar equivalences.

Autres contacts

Enseignant : Pascal SCHRECK