Descriptif
Objectifs pédagogiques
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.
- Travaux pratiques : 3
- Travaux dirigés : 3
- Leçon : 10
Diplôme(s) concerné(s)
Format des notes
Numérique sur 20Pour 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.