v2.11.0 (5449)

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

Domaine > Informatique.

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)

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 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é

Programme détaillé du 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).
Veuillez patienter