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 20Littérale/grade européenPour 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.