Présentation

Attention ! Ce module est un module sans doute un peu plus difficile que les autres. Les principales raisons sont les suivantes :

• c'est un module assez théorique qui se base sur un certain nombre de concepts mathématiques ;
• il demande de mettre en oeuvre des raisonnements logiques et il faut d'être capable de faire des preuves ;
• de ce fait, il est nécessaire de maitriser un minimum les notations mathématiques les plus courantes.

Ceci dit, tout au long de ce cours, certains théorèmes ou lemmes sont démontrés. Il n'est pas demandé de connaitre "par coeur" ces démonstrations mais de comprendre les procédés mis en oeuvre. Par contre, il faut être capable d'expliquer toutes les méthodes et les résultats que vous obtenez dans les différents exercices. Encore une fois, le plus important est de comprendre les méthodes présentées et pourquoi elles fonctionnent.

Quelques conseils pour bien réussir :

• toujours être capable de justifier ce que vous avancez ;
• bien vérifier la cohérence de vos "calculs" par rapport aux données initiales et aux objectifs visés ;
• travaillez bien les différentes méthodes présentées (bien connaitre ce qui se passe et pourquoi).

Ce cours est normalement accompagné par un tuteur sur un semestre universitaire. Durant ce semestre, des devoirs sont proposés et corrigés par ce tuteur. A titre d'exemple, les devoirs 2008 sont disponibles ici en version PDF : devoir n°1, devoir n°2, devoir n°3. Si vous suivez ce module dans un centre e-miage, veuillez vous rapprocher de votre tuteur afin d'avoir les devoirs du semestre courant.

Le cours en PDF est UN PEU ancien. J'ai corrigé une ou deux erreurs. Je ne compte pas faire une nouvelle version PDF (lourd à faire) car la version en ligne est bonne (Attention, il semble que ce cours B209 ne soit pas bien affiché avec Internet Explorer ; par contre, il n'y a pas de problèmes avec Firefox ou tous les navigateurs de la famille Mozilla).

Bibliographie complémentaire

Cette page propose une bibliographie complémentaire au cours.

Sont listés ici les ouvrages majeurs qui ont servi à construire ce cours ou ceux, parus après, qui auraient pu servir :

• Patrick Bellot & Jacques Sakarovitch, "Logique et automates", série Manuel d'Informatique, Ed. Ellipses, Paris, 1998, ISBN 2-7298-689

• Patrice Séébold, "Théorie de automates : méthodes et exercices corrigés", série Passeport pour l'informatique, Ed. Vuibert, Paris, 1999, ISBN 2-7117-8630-7, www.vuibert.f

• Peter Linz, "An Introduction to Formal Languages and Automata", Jones and Bartlett Publishers, 2006, ISBN 0-7637-3798-4

Plan du cours B209 : Langages et automates

• Chap. 1 : présentation du module / Introduction ;
• Chap. 2 : présentation des bases de la théorie des langages formels ;
• Chap. 3 : les langages rationnels ;
• Chap. 4 : les grammaires ;
• Chap. 5 : les automates à nombre fini d'états ;
• Chap. 6 : équivalence entre les langages rationnels et les langages reconnaissables ;
• Chap. 7 : applications ;
• F.A.Q.