Vous êtes ici :

Discipline(s) : Electronique, Informatique, Mathématiques, Sciences et technologies

UE4 - S5: Langages Formels | P.Informatique

Semestre Semestre 5
Type Obligatoire
Nature UE
Volume horaire total 40h
Volume horaire CM 20h
Volume horaire TD 20h

Domaine(s) LMD

Informatique, Mathématiques - Informatique

Langue(s) d'enseignement

Français

Responsables

Objectifs

  • Descriptions plurielles (par automates, grammaire...) de l'ensemble des mots constituant un langage formel.
  • Identification de la classe d'un langage donné (rationnel/algébrique). 
  • Amélioration de la clarté de leur expression écrite.
  • Appréhension de la notion de décidabilité.

Contenu

  1. Introduction: la théorie des langages et ses applications en Informatique
  2. Le monoïde libre
  3. Langages reconnaissables
  4. Automate minimal
  5. Décidabilité: problèmes décidables et indécidables en théorie des langages. 

Appartient à

Bibliographie

Concepts fondamentaux de l’informatique, A. Aho, J. D. Ullman (Dunod, 1996)
La machine de Turing, A. Turing, J-Y. Girard (Seuil, 1999)
Introduction to automata theory, languages and computation, J.E. Hopcroft, J.D. Ullman (Addison-Wesley, 2007)

Contrôles des connaissances

Contrôle de connaissances Terminal/Projets.