Introduction aux automates finis et expressions rationnelles

Juste pour préciser en début de ton texte :

Le lien vers la source ne mène nul part.

Je ne trouve au contraire que ça peut avoir un intérêt direct. C'est bien de présenter des notions théoriques, mais ce qui est encore mieux c'est de savoir s'en servir dans la vie. Donc je pense que ce n'est pas inintéressant de s'intéresser à comment représenter un automate et ses transitions efficacement en mémoire.

Oui c'est sûr, mais l'idéal serait d'avoir ça avec un langage graphique non pas en C comme je l'ai proposé .

C'est intéressant mais encore une fois, ce n'est pas mon but. Après, ça peut faire l'objet d'une piste de réflexion proposée dans la conclusion.

Le lien est corrigé (mais la bêta n'est pas à jour ).

Non mais je pensais que tu étais parti sur un big-tuto. C'est sur que si tu fais un simple tutoriel ça ne vaut pas le coup de parler d'implémentation (ou bien à titre d'ouverture). Je suis un peu à l'ouest en ce moment (en réalité je suis plutôt au Sud mais bon…).

Le lien est corrigé (mais la bêta n'est pas à jour ).

Penses à mettre à jour la beta à chaque fois que tu modifie ton tutoriel (il y'a un bouton pour ça) car la beta est une version figée de ton tutoriel. Si la beta se mettait à jour toute seule en même temps que tu écris tu n'aurai plus de controle sur ce que tu veux garder en brouillon (ne pas montrer) et ce que tu souhaite montrer (beta).

Pour information aussi quand tu publies le lien de ton tuto en beta, tu dois absolument copier toute l'url (avec le ?version=xxxxxxx) sinon dès que tu modifiera ton brouillon le lien deviendra innaccessible, car la dernière version en date ne sera plus équivalente à ce qui a été marquée en beta.

@firm1 : Merci beaucoup pour les explications, je comprenais pas bien comment ça marchait !

@Saroupille : Effectivement, on s'était visiblement pas bien compris. Non, le cours au complet fera environ deux ou trois fois la taille qu'il fait actuellement… Donc pas vraiment un big-tuto ! Mais tu m'as quand même fait des remarques pertinentes.

Pour dessiner les automates, tu as pensé à utiliser Graphviz ? Je sais pas si on peut l'installer sous Windows, mais c'est super pratique pour dessiner des graphes.

EDIT : pour info, voilà comment installer et s'en servir : http://cyberzoide.developpez.com/graphviz/

Rebonjour,

Après quelques réflexions d'ordre pédagogique et sur mon enthousiasme, je reviens vers vous avec une refonte de mon idée de cours. J'ai finalement rejoint plusieurs des commentaires précédents et choisi d'aborder en parallèle les expressions rationnelles et les automates finis, en prenant comme fil rouge les questions basiques que l'on est amené à se poser aux prémisses de la science de la compilation. Voilà ce que ça donne.

La suite du plan du cours est définie sur papier, la deuxième partie réutilisera des éléments de ce que j'avais rédigé plus tôt mais en les réadaptant à un ton que je trouve désormais plus défini, une ligne directrice plus claire. Le cours sera finalement un mini-tuto assez long dans la lignée de ce que vous pouvez lire jusqu'ici (à peu de choses près).

Voilà, tous les commentaires (notamment des personnes actives ici précédemment) sont bienvenus !

Edit : mathedit, merci pour le lien.

Juste pour dire que ton tuto m'a fait commencé un tuto d'introduction sur la théorie des ensembles. Je ne prédis pas l'avenir, mais il se peut que plusieurs tutoriels théoriques commencent à fleurir. Afin d'éviter de la redondance pour expliquer ce qu'est un ensemble et pour que ce soit accéssible à un maximum de gens, j'ai donc voulu créer ce tutoriel.

C'tout.

Bonne continuation

En lisant l'intro du tuto, je pense qu'il faudrait peut être détailler point par point ce qu'est un langage et un alphabet (détailler avec une liste : alphabet, syllabe, mots), avec pourquoi pas un parallèle avec le dictionnaire français, composé de mots, composés de syllabes, composées de lettres, plutôt que de parler de l'alphabet binaire (c'est plutôt abstrait, la notation {0,1} nécessite de connaître les expressions régulières, le tuto pourrait permettre de comprendre les expressions régulières, justement).

Questions subsidiaires :

• Le lemme de pompage est au programme ou c'est trop compliqué / hors sujet ?
• Est-ce que tu vas parler des automates à pile et des grammaires ou c'est hors sujet ? Il pourrait être intéressant, à mon avis, à la fin du cours, de montrer par un exemple simple, que le formalisme des automates à états finis est limité par rapport à la machine de Turing ou aux automates à pile : en utilisant l'exemple de l'expression rationnelle qui pourrait reconnaître n'importe quelle chaîne à condition que deux caractères se répètent le même nombre de fois à l'intérieur (possible avec un automate à pile mais pas un automate à états finis). Ça pourrait faire le lien vers un autre tuto, plus complexe, sur les grammaires (avec un peu de Flex/Yacc parce que c'est marrant à faire).

(note personnelle : un tuto Makefile est prévu par quelqu'un ?) EDIT : ah il y en a un sur OC

@Saroupille : parfait ! C'est vrai que ce site semble commencer à prendre une orientation vers un peu plus de cours théoriques, donc des bases de théorie des ensembles, ça pourra toujours servir.

@mathedit : bonne remarque pour le début, il est vrai que l'alphabet $F_2$ est assez évident pour moi mais c'est pas forcément l'exemple le plus adapté pour un débutant. Le lemme de pompage (je le connaissais pas sous ce nom, pour moi c'est le lemme de l'étoile) est au programme, j'aimerais l'aborder dans la troisième partie de manière simple et imagée, c'est mon gros défi pour ce cours. Pour ce qui est des grammaires et automates à piles, c'est hors sujet ; d'une part parce que je ne maîtrise pas assez la question, d'autre part parce qu'à mon sens ça rentre plus dans le cadre d'un cours plus complet sur les bases de la compilation. Cependant, à un moment ou à un autre (plutôt dans la dernière partie) je ferai bien voir qu'on ne peut pas tout décrire avec les expressions rationnelles…

En fait je voulais faire une troisième partie qui aborde la conversion d'une expression rationnelle en automate fini et inversement, et présente du coup le théorème de Kleene. L'explication du lemme de l'étoile permettrait de montrer ensuite que certains langages ne sont pas reconnaissables / rationnels, et je proposerais en conclusion des pistes vers la suite (notamment un très bon tuto que j'ai découvert sur progdupeu.pl à ce sujet).

Edit : bêta mise à jour, la première partie est à peu près finie (hors coquilles).