Noam Chomsky. (Photo credit: Wikipedia)

Automates et langages

Le module « Automates et langages » vise à introduire les bases de la théorie des langages, des automates ainsi que les principales notions sur les compilateurs. Il permet d’appréhender un certain nombre de techniques fondamentales :

• de nouvelles techniques de programmation (notion de programmation dirigée par la syntaxe)
• le contrôle de validité
• la compréhension et optimisation de nouveaux outils proposant l’utilisation des expressions régulières (Perl, PHP, JDK 1.4…)
• la présentation de bases pour des techniques de CSI (modélisation dynamique en UML) et de compilation (analyseurs lexicaux).
• …

Ce cours propose aussi d’habituer l’étudiant à des formalisations et démonstrations utiles pour d’autres cours.

Nous y définissons les notions suivantes : vocabulaire, langage, grammaires, classification de Chomsky, langages relationnels, expressions régulières, machine de Turing, automates déterministes et non-déterministes. Nous présentons aussi bien les bases théoriques nécessaires à la bonne compréhension de ces notions que des algorithmes de base permettant de les manipuler. En particulier,nous nous attachons à présenter les outils permettant de construire un analyseur de chaînes de symboles à partir d’une ou plusieurs expressions décrivant leur construction (le langage).

Pour comprendre les notions abordées dans ce modules, il est nécessaire de bien maitriser les concepts suivants : théorie des ensembles, démonstration par l’absurde et démonstration par induction, algorithmique, programmation impérative (éventuellement programmation objet Java).

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).