Langages formels

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

Contact(s)

Contact(s) administratif(s)

Remi LEGRAND (remi.legrand @ umontpellier.fr)