Introduction aux automates finis et expressions rationnelles

Bonjour à tous.

Complètement enthousiasmé que je suis par les outils de rédaction que propose ce site, ainsi que par l'idée de contribuer, de créer du contenu, je me suis lancé dans la rédaction d'un petit chose sur, comme mon titre l'indique, les automates finis. Je me suis délibérément inspiré de mon cours d'option info en prépa, qui donne une base assez intéressante sur le sujet, et suffisante pour pouvoir aller explorer plus loin et découvrir des choses passionnantes - à mon goût.

Pour l'instant, je n'ai pas suffisamment de contenu pour proposer une bêta ouverte mais un tel tutoriel vous semblerait-il intéressant et pertinent ? Il sera assez court, aussi peu orienté que possible vers le formalisme sans pour autant être un enchaînement d'exemples artificiels. Mon ambition est simplement d'exposer quelques concepts de base sur les automates, à titre de curiosité pour le lecteur qui comme moi, s'intéresse un peu à l'info théorique.

J'attends vos avis !

Edit : la dernière version de la bêta est ici. Finalement, le tuto condensera une approche introductive de la première lasagne de la hiérarchie de Chomsky (kamoulox), soit des éléments sur les expressions rationnelles ET sur les automates.

Merci ! En fait j'envisage même à terme de tutoriser tous mes cours d'info de l'année passée, je pense que j'aurais de quoi faire trois mini-tutos bien mastocs (un sur l'induction, un sur la théorie des langages et celui-ci).

Oo ça serait une bonne idée en effet. Je suis sur que des lecteurs ne manqueront pas.

Tu me fais penser que j'ai un très bon cours de Java provenant de mon BTS SIO, je pense que je vais faire de même

Pour ce qui est de $\LaTeX$ et des automates, je prends le parti de les dessiner à la main, de toute façon il n'y en aura pas 50 puisque je voudrais faire un cours plutôt… court.

De fait, le plan de ce que j'avais en tête rejoint en partie celui que tu as donné, mais je voulais moins m'attarder sur les langages (quitte à faire d'autre part, où à te laisser faire tiens, un cours à part sur le sujet). Je donnerais donc en introduction la définition rapide d'un langage, d'un mot etc., puis expliquerais ce qu'est un automate (en prenant l'exemple d'une machine à café ). Dans une deuxième partie, je donnerais quelques propriétés des automates (émondés, complets, déterministes) ainsi que l'algo de déterminisation qui me semble intéressant (ce que tu appelles minimisation, je crois). Et enfin, dans une troisième partie, j'aimerais aborder le lemme de l'étoile, qui me semble très intéressant en ceci qu'on peut en donner une explication et en montrer l'intérêt sans trop théoriser autour des expressions rationnelles (ce que je voudrais éviter autant que faire se peut).

Du coup, je n'aborderais pas le passage AF -> expression et réciproquement (d'ailleurs j'aurais plutôt fait ça avec le lemme d'Arden dans un sens, et la méthode fournie par la démo du théorème de Kleene dans l'autre), parce que ça nécessiterait de poser pas mal de définitions et de formalisme autour des langages et des expressions rationnelles. Mon but est vraiment de tenter d'aborder les automates pour eux-mêmes, et de montrer un peu ce qu'on peut faire avec, en se détachant au maximum du cadre de la théorie des langages, même si je sais bien que les deux sont très liés.

Tiens au passage, le cours de mon prof sur lequel je m'appuie est dispo en ligne même s'il faut avoir l'adresse pour le trouver, ici.

Edit : allez, une petite bêta !

Je suis tout à fait d'accord, je pensais faire pareil pour les explications de Langages et Mots, ça sert à rien de partir sur des trucs compliqués. Par contre quand je parle de détermination c'est qu'il existe uniquement 1 transition par lettre pour chaque état. Et minimisation c'est faire en sorte de se retrouver avec un automate le plus petit possible. Je me disais que les 2 dernières parties pouvaient être utile pour montrer des exemples d'applications (par exemple avec des expressions régulières), et également parce que c'est ce qui manque cruellement sur internet, par exemple Yamada est introuvable sur internet.

Au pire je ferais une partie application dans un autre tuto

Ah oui c'est vrai, que l'algo de déterminisation n'aboutit pas forcément à un AF minimal, j'étais déjà tombé sur ça.

Mais clairement, si tu es motivé pour fournir ça dans un autre cours ça serait tout à fait bienvenu, parce que je ne pense vraiment pas l'aborder dans le mien (difficile de parler du passage AF -> expression sans expliquer ce qu'est une expression rationnelle et tutti quanti…).

(D'ailleurs je connais pas Yamada, ça consiste en quoi ?)

Je voudrais juste apporter un petit avis. Les automates finis ont vraiment beaucoup d'applications en informatique, et pas seulement théorique. Je pense que ce ne serait pas une mauvaise idée de dissocier un tutoriel un peu plus pratique sur les automates et un tutoriel un peu plus théorique.

Par exemple pour la minimisation/détermination , il y a des façons simples de voir ces algorithmes, sans avoir besoin de toute la théorie derrière, prouver la correction et la terminaison des algorithmes etc…

Pour un premier tutoriel sur les automates à états finis, je pense que ça ne serait pas une si mauvais chose d'être un peu plus superficiel et d'introduire avant tous les motivations et les applications avant de voir l'aspect algorithmique derrière. En tout cas, c'est une excellente initiative que je tenterai de suivre.

Bin, merci beaucoup. Tu peux déjà aller voir la bêta et donner ton avis sur le peu de contenu qu'il y a encore, il sera bienvenu. Je pense enrichir le tuto dans la soirée et commit sous peu.

C'est difficile de juger sur aussi peu de contenu. Je fais parti des gens qui préfèrent d'abord avoir une motivation derrière la tête quand j'apprend de nouvelles choses, je trouve que c'est toujours un peu plus parlant et ça permet de savoir (à peu près) vers où on va.

Et c'est là où je diverge un petit peu avec toi, c'est que je trouve que ça ne serait pas un mal de parler d'expressions régulières avant des automates. C'est un truc qu'un informaticien va apprendre à s'en servir toute sa vie, et s'il peut connaître la machinerie qu'il y a derrière, ce n'est pas un mal.

A partir de là, je trouve, que ça devient plus naturel de parler d'automates puisque tu vas avoir un fil rouge qui sera : mais comment je peux reconnaître une expression regulière par exemple ? Ou l'inverse ?

Et ça te fais en plus, une excellente source d'exemples qui ne sortirons pas de nulle part.

Après dans ce que tu as fait il y a quelques imprécisions, je prend au pif un paragraphe mais par exemple : $\Sigma^*$ représente l'ensemble des mots finis y compris $\varepsilon$.

C'est dommage de mettre un tutoriel en Beta si tôt, alors qu'il y a trop peu de contenus.

Mmmh je ne suis pas persuadé d'avoir compris le fonctionnement de la bêta, mais mon tuto n'est accessible que si j'en donne le lien non ? Ou aussi depuis ma page de profil ? En tout cas je voulais exactement avoir le genre de retours que tu me donnes, alors ça me semble une bonne idée de l'avoir publié en bêta.

Pour ce qui est des imprécisions, il y en a certainement d'autres que celle que tu évoques et je me relirai plusieurs fois avant de tenter de publier quoi que ce soit, mais en l'occurrence c'est plus un choix rédactionnel qu'une faute. Il me semble pour le moment inutile de préciser que $\Sigma *$ contient aussi le mot vide, et je ne le préciserai pas tant que la suite du tuto ne le nécessitera pas explicitement (par exemple, je ne suis pas sûr de parler des $\epsilon$-transitions mais dans ce cas, il faudrait que je précise ce qui précède). Ne t'inquiète pas, je suis tout à fait capable de fournir quelque chose de plus rigoureux que ce que j'ai fait là, mais j'essaye justement d'avoir une approche plus didactique, moins rebutante qu'un cours de prépa (cf. le pdf que j'ai linké plus haut). Faudra voir si ça reste viable au fur et à mesure que le tuto avance, bien entendu.

Pour ce qui est des expressions rationnelles (et pas régulières ), je t'avoue que j'hésite encore. Ça me semble un pari intéressant de rédiger un cours sur les automates sans en parler, et pédagogiquement pas dénué de sens : en effet, et cela rejoint ma volonté de "vulgarisation", il est impossible d'aborder les expressions rationnelles correctement sans un formalisme qui va au-delà de ce que j'envisage pour ce tuto. Après, ça reste sujet à modifications et si je me rends compte que je n'arrive vraiment pas à rédiger quelque chose d'intéressant et instructif sans en parler, je reverrai ma méthode.

Mais au final, ce que je cherche à produire c'est plus un long article de vulgarisation / curiosité, qu'un réel "tutoriel" trop axé sur le pratique et sur l'alignement d'exemples plus ou moins rébarbatifs.

Je pense que nos points de vue divergent. Mais j'ai aussi du mal à comprendre ce que tu entends par le terme vulgarisation ? Car j'ai l'impression que tu as, excuse moi de l'expression, le cul entre deux chaises. D'un côté, tu veux que ce soit accéssible à plein de gens, et l'intention et louable, mais à côté tu introduis un formalisme douteux pour rester dans un cadre formel.

Mais j'ai vraiment du mal à comprendre ce que tu cherches à vulgariser ? Pour moi un bon exemple de vulgarisation, ça va être Etienne Klein qui t'explique ce qu'est le temps où la relativité restreinte sans un soupçon d'équations. Et après une heure, j'aurais l’impression d'avoir un peu mieux compris ce que c'était. C'est sur, je ne pourrais pas utilisé ce que j'ai appris dans ma vie de tous les jours, mais je me sentirais un peu moins con. Après tout, on est confronté à la question du temps tous les jours.

Pour un développeur, les automates, c'est quand même aller regarder un peu sous le capot d'une voiture et voir comment ça fonctionne. Mais là c'est comme si tu prenais n'importe quel moteur, que ce soit pour une voiture, un bâteau, un robot etc… et que tu m'expliquais grosso-modo son fonctionnement. Or, moi dans la vie de tous les jours, je me sers d'une voiture et pas d'un bâteau et si je veux connaître le fonctionnement d'un moteur, ça sera plutôt pour une voiture car je m'en sers tous les jours. A l'inverse, l'ingénieur, il devra plutôt s'intéresser au fonctionnement de n'importe quel moteur car il ne saura pas sur quel type de moteur il devra travailler.

Je ne sais pas si ma métaphore est bien choisie, mais si tu veux faire de la vulgarisation, c'est la même chose. N'importe quel développeur sera un jour confronté aux expressions régulières, et si tu veux lui expliquer comment ça marche tu vas passer par les automates, c'est certains. Mais de quel formalisme as-tu besoin ? Des ronds avec des flèches ça passe très très bien aussi pas besoin de se compliquer la vie avec la théorie des ensembles.

Donc je pense, bien que tes intentions soient louables, que tu t'engages sur une pente dangereuse. Ton cours ne sera pas forcément mauvais, mais il ne sera pas bien adapté pour ton public. D'un côté le développeur curieux qui veut regarder la machinerie, et de l'autre le théoricien qui lui veut vraiment savoir comment tout ça fonctionne, et le théoricien c'est un chieur, il veut de la précision.

En tout cas je ne sais pas vraiment à quoi m'attendre. Peut-être que je me trompe, et je l'espère, mais cette première impression me semble bizarre.

Et attention, je ne veux pas du tout te décourager ou quoi que ce soit, car je pense qu'un tutoriel sur les automates à états finis c'est génial, mais quand on comment à s'engouffrer dans la théorie, je pense qu'il faut y réfléchir au moins à deux fois avant de se lancer.

Mmmh. Le moins qu'on puisse dire, c'est que tu me donnes à réfléchir. Alors je vais faire ça, écrire aussi, et je te propose de continuer cette discussion quand j'aurai mis certaines choses au clair et abouti à un peu plus de contenu !

En tout cas, merci pour ton temps.

Bonjour Alkareth,

Il y a quelques années j'ai implémenté une librairie C calquée sur le principe des automates finis comme tu les appelles (ou machine à états finis comme je les appelle) .

La lib te permet de construire un système d'états et de transitions complexes en langage C.

Ca pourrait être un cas d'application intéressant pour ton cours, tu me diras si ça t'intéresse.

Oh ! Ça m'intéresse à titre de curiosité personnelle, mais je crains que ça ne rentre pas dans le cadre de mon cours (quoique, en annexe…). Je te tiendrai au courant, je suis justement en train d'avancer la rédaction.

Merci !

@uknow : tiens je te retrouve ici. Juste une question sur ton commentaire sur la terminologie. Je pensais que la différence entre machines et automates c'était que le premier produisait une sortie et pas le dernier. Comme les machines de Moore où de Mealy.

Pourquoi tu ne fais pas cette distinction ?

Et sinon Alkreth, pour faire des automates en LaTeX tu as GasTex. Et tu peux utiliser JFLAP sinon, au lieu de les faire à la main.

Merci, je vais chercher par là (de toute façon je dessinerai proprement mes automates quand j'aurai fini de rédiger le texte).

Pour ce qui est de la terminologie, je peux me tromper mais je n'ai pas souvenance d'une telle distinction. Les machines de Turing par exemple, ne produisent pas forcément de sortie.

Edit : bêta mise à jour. La première partie du cours est terminée dans les grandes lignes.

Je parlais au niveau des automates. Et si, une machine de Turing, sa sortie c'est le ruban. Après tu choisis de t'en préoccuper ou pas, mais il est là.

Ça n'a pas d’intérêt direct pour le cours effectivement, mais en cas d'application, ou plutôt en outil ça peut permettre de faire des essais rapides. Mais bon à réfléchir, je peux te fournir du contenu si jamais.

Bon courage.

@Saroupille : je ne connais pas de nuance dans la définition de l'une et de l'autre, par contre les machines de Moore et de Miley en sont deux déclinaisons différentes l'une de l'autre en effet.