Langages formelsCode de l'UE : HLIN502
Présentation
Mots et langages : Concaténation. Fermeture de Kleene. Sous mots. Ordre sur les mots.
Grammaires non contextuelle : Productions. Chaînes de dérivation. Lemme fondamental. Preuve sur les grammaires. Arbre de dérivation. Grammaire ambiguë. Langage de Dyck et de Lukasiewicz.
Automates : Définition et représentation. Fonction de transition itérée étendue. Chemin et trace. Preuve sur les automates. Indéterminisme, ?-transitions. Minimisation. Théorème de Kleene. Lemme de la Pompe.
Expressions rationnelles : Langage associé. Équivalence entre automate et expression rationnelle. Variation des états d'entrée/sortie.
Objectifs
Le but de cet enseignement est de :
-
Maîtriser les concepts de langage formel, grammaire, automates et expressions régulières.
-
Acquérir l'aptitude à manipuler des outils formels et établir des preuves.
-
Savoir faire des raisonnements par récurrence.
-
Savoir mettre en œuvre les concepts étudiés afin de faire des preuves d'algorithmes
Volume horaire
- CM : 16.5
- TD : 33
- TP : 0
Diplômes intégrant cette UE
En bref
Crédits ECTS 5
Nombre d'heures 49 HE
Période de l'année
S5
Méthode d'enseignement
En présence
Langue d'enseignement
fr