Les automates finis

Salut à tous,

Après un peu de réflexion, j'ai commencé à écrire une initiation à l'informatique théorique avec les automates finis. Même si vous n'y connaissez rien au sujet je suis très preneur d'avis pour améliorer ce que j'ai déjà écrit(quelques heures des rédaction déjà).

Ma grande peur est que ce tuto soit trop compliqué et demande des connaissance avancées en maths… Comme je suis le nez dedans, je ne vois peut être pas les points compliqués pour quelqu'un d’extérieur au domaine. Je veux vraiment que ce tuto soit adressé à tout le monde et donne envie à n'importe qui de s'intéresser à l'info théorique. N'hésitez donc pas à me signaler tout point qui vous paraitrait peu clair et/ou mal expliqué, c'est le but de cette bêta !

Je recopie ici l'intro :

Ici vous allez entendre parler d'informatique théorique. Quelle drôle d'idée, de l'informatique sur papier, sans toucher à un ordinateur !
Et pourtant, l'informatique théorique c'est un peu comme les maths pour la physique : se creuser un peu la tête sur des notions théoriques permet de résoudre ensuite des problèmes bien concrets.

Dans ce tutoriel, rien de concret, mais une introduction au sujet avec les automates finis. Ce sont des modèles permettant de représenter un machine effectuant des calculs très simples. Mais en les utilisant correctement, on peut effectuer de nombreuses opérations.

Ce tuto se veut une introduction au sujet, toutes les définitions et démonstrations ne seront pas détaillées afin de ne pas vous perdre ! Si vous souhaitez aller plus loin ou voir ce qui est omis ici, je vous invite à consulter les références données en conclusion.

Tout d'abord il faudra présenter la notion de langage, d'automate pour ensuite voir ce qu'on peut faire avec. Le dernier chapitre est une ouverture sur des notions un peu plus complexes, qui présente les limites de ce modèle.

Bonne lecture .

Merci d'avance !

J'ai pas le temps de lire dans les détails tout de suite mais j'ai survolé la première partie. Pour ajouter un aspect plus concret au tutoriel, tu pourrais donner plus d'exemples de mots histoire de montrer que la théorie des langages a des applications un peu partout (une phrase peut être un mot, un fichier C aussi, une image aussi etc…).

Salut,

Je connais un peu les automates finis, voilà ce qui pourrait être intéressant je pense (je n'ai pas lu tout le tutoriel).

• Application des automates finis comme l'a dit Bibibye.
• Exemple de construction d'automate (on peut construire un automate qui reconnaît les multiples de certains nombres suivant leur écriture en binaire).//au temps pour moi je viens de voir qu'il y a une partie avec des exemples.
• Avoir une partie sur la description du langage (je suis plus sûr du terme mais dans ton exemple ce sont les mots qui commencent par ab et on peut écrire (ab(a+b)*)).
• La notion d'automate complet.
• Opération sur les automates: concaténation, union, transition, complémentaire, détermination, minimisation (sauf si tu considères cela trop complexe mais concaténation/union/transition/complémentaire sont assez simple à expliquer je pense).

Juste une petite remarque (je n'ai pas lu en détail ton tutoriel). Le format d'un tutoriel est assez fléxible et permet de sortir juste du contexte de lire du texte.

Pour dérouler des automates, pourquoi tu n'utiliserais pas une video ? Ok, ce n'est pas très portable pour d'autres formats, alors pourquoi tu conseillerais pas à ton lecteur de télécharger un logiciel afin qu'il puisse en manipuler par lui-même ?

Ah ! Je n'avais pas vu ce tutoriel, mais ça fait un moment qu'une idée de tuto sur les applications d'algos que l'on peut associer aux automates dans des programmes de la vie réelle me trotte dans la tête.

Par exemple, rechercher une chaîne de motifs avec l'algorithme de KMP, détecter les coups spéciaux dans un jeu à la Street Fighter grâce à l'algorithme d'Aho-Corasick, génération d'Automates Finis Non déterministes à partir d'expressions régulières avec l'algorithme de Thompson, "déterminisation" d'un automate, etc..

Effectivement, ton tutoriel livre une introduction très formelle par rapport à ce que j'avais en tête sur le sujet.

Je prendrai le temps de le lire pour te faire un retour plus complet plus tard.

Merci à tous pour vos retours !

Je vais essayer de répondre à tout.

Déjà pour le coté peu pratique, souligné par nohar et Bibibye je vais essayer de changer ça. Clairement je ne veut pas tomber dans un truc abstrait qui fasse fuir tout le monde. Je vais regarder du coté de ce que tu as dit nohar, il doit en effet avoir moyen de dire plein de choses. Mon problème est ma préférence: j'adore tout ce qui est décidabilité, etc.. donc absolument pas concret.
Mon second problème est la taille du tuto. Je ne me vois pas présenter des algos liés aux automates sans définir un automate. Et y a-t-il une manière moins formelle de présenter les automates qu'en présentant d'abord alphabet, langages.. comme je le fait ? J'ai l'impression que non mais ma vision est très biaisée là dessus (plongé là dedans à longueur de journées ça ne me choque absolument pas…).
Si vous avez des remarques sur ma manière de définir tout ce blabla, je suis là pour ça !

Concernant la détermination et générations d'AFND à partir des expressions j'y pensais, je ne sais juste pas où je vais caser ça dans mon plan pour le moment.

Avoir une partie sur la description du langage

Ça c'est prévu dans "langages rationnels".

La notion d'automate complet.

Théoriquement c'est très utile mais pour une utilisation "avec les mains" je suis moins sûr.. tu as une idée plus précise de ce que tu attends dans cette notion ?

Opération sur les automates

Je voulais le faire au début, puis je me suis dit que ça n'était pas le plus intéressant. Je pourrais éventuellement en parler dans la dernière partie, puisque c'est une technique souvent utilisée pour montrer qu'un langage n'est pas rationnel.

Et enfin j'aime beaucoup ton idée Saroupille, je vais bosser pour au moins faire des gif animés pour la lecture de mots dans l'automate. Ca rendra la lecture vraiment dynamique, merci . (Le truc c'est que c'est assez long à faire puisque je génère les images une par une). D'ailleurs je ne sais pas ce que tu entends par "un logiciel afin qu'il puisse en manipuler par lui-même ", je n'utilise pas de logiciel pour gérer/simuler des automates puisque je n'en connais pas, si tu pensais à quelque chose en particulier je suis preneur .

Merci encore !

Je n'ai pas de réelle expérience en automates donc je ne peux pas te conseiller sur l'approche à adopter, mais ce cours, bien qu'un peu indigeste, me semble assez complet en ce qui concerne les notions théoriques.

AMHA, commencer par présenter un automate fini comme une simple machine qui lit des symboles et décide si une suite de symboles est "valide" ou non (en utilisant des graphiques, comme dans la section sur la "vue intérieure" du tutoriel) est une première approche intéressante, quitte à repasser plus loin pour formaliser certaines notions. Ça permet au lecteur de se construire une intuition avant de s'attaquer aux définitions plus formelles.

Une approche bottom up où on commence avec la base (alphabet, langage) est très bien dans le cadre académique (les étudiants sont a priori intéressés, vont suivre tous les cours, et sont normalement assez mathématiquement matures pour commencer avec les définitions), mais dans le cadre d'un cours sur le web, où le lecteur a l'opportunité de naviguer ailleurs à tout moment, je ne sais pas si c'est la meilleure approche.

le seul logiiel que je connaisse s'appelle JFLAP.

Je vois que le tutoriel est en béta depuis très longtemps. Y a-t-il toujours une volonté de le rédiger?

C'est marrant, j'envisageais dernièrement d'écrire un truc sur le sujet.