SynapseS

Descriptif

Ce cours constitue une introduction à la théorie des langages formels, destiné à introduire des concepts utiles dans de nombreux cours d'approfondissement en informatique et en réseaux.

Objectifs pédagogiques

On y introduit les notions générales de mot et de langage. On présente ensuite le formalisme des expressions régulières, permettant de décrire une classe importante de langages: les langages rationnels. Les automates à état finis sont ensuite introduits, ainsi que les quelques algorithmes afférents (déterminisation, minimisation...). On montre également comment ces machines permettent de reconnaître les langages rationnels. On présente ensuite la notion de grammaire formelle, et son utilisation pour décrire des langages. Deux sous-classes de grammaires sont étudiées: les grammaires régulières, dont on constatera l'équivalence avec les expressions régulières; puis les grammaires
hors-contexte. Ceci entre dans le cadre de l'étude de la hiérarchie de Chomsky. On donnera une brève introduction à l'analyse de grammaires hors contexte. Finalement, la notion de (semi-)décidabilité d'un langage est introduite et illustrée.

18 heures en présentiel (12 blocs ou créneaux)

réparties en:

Travaux pratiques : 3
Travaux dirigés : 3
Leçon : 10

Diplôme(s) concerné(s)

Diplôme d'ingénieur

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

Vos modalités d'acquisition :

Contrôle continu (TP, TD)

Contrôle de connaissance à la fin de l'unité d'enseignement.

Unité d’enseignement validée lorsque la note finale de l’UE est supérieure ou égale à 10. Pour chaque unité d’enseignement validée, des crédits ECTS associés sont acquis, et le sont de manière définitive.

L'UE est acquise si Note finale >= 10

Crédits ECTS acquis : 1.5 ECTS
Crédit de BCI acquis : 1.5

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

Dans le polycopié disponible sur le site pédagogique, sont au programme du cours (et de l'examen) :

- Généralités sur les langages (chapitre 1) ; les notions d'ordre, de quotient, de distance ne sont pas spécifiquement au programme et seront réintroduites dans l'examen si elles y sont utiles

- Langages rationnels, expressions rationnelles, automates (chapitres 2 et 3, cf. aussi TD 1, TP 1)

- Introduction aux grammaires génératives et à la hiérarchie de Chomsky (chapitre 4)

- Grammaires et langages hors-contexte : définitions, arbres de dérivation, lemme de pompage pour les grammaires hors-contexte, problématique de l'analyse de grammaire (chapitres 4 et 5, cf. aussi TD 2, TP 2)

- Notions de calculabilité (chapitre 9) ; la définition formelle des modèles de calcul (machines de Turing) n'est pas au programme

Le chapitre 6 est partiellement couvert en cours mais n'est pas au programme de l'examen. Les chapitres 7 et 8 ne sont pas au programme de l'examen. Le chapitre 10 (compléments historiques) n'est pas au programme mais pourra être utilisé pendant le cours.

Mots clés

Mot et langage, formalisme des expressions régulières. Langages rationnels, automates à étéat finis. Grammaires formelles (régulières et hors-contexte).

Enseignement scientifique & technique - INF105 : Théorie des langages

Domaine > Informatique.