v2.11.0 (5932)

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:
  • Activité artistique & musique : 10
  • Travaux Dirigés : 3
  • Travaux Pratiques : 3

Diplôme(s) concerné(s)

UE de rattachement

Format des notes

Numérique sur 20

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

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10

Le coefficient de l'UE est : 12

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).
Veuillez patienter