Dans quelle mesure la théorie des automates est-elle pratique?

Il existe toujours un moyen d’appliquer dans des domaines liés à l’informatique théorique. Mais les manuels scolaires et les cours de premier cycle n'expliquent généralement pas pourquoi la théorie des automates est un sujet important et si elle a encore des applications dans la pratique. Par conséquent, les étudiants de premier cycle pourraient avoir du mal à comprendre l’importance de la théorie des automates et penser qu’elle n’a plus aucune utilité pratique.

La théorie des automates est-elle encore utile dans la pratique?

Devrait-il faire partie du programme de premier cycle en CS?

1. Avez-vous déjà utilisé un outil tel que grep / awk / sed? Les expressions régulières constituent le cœur de ces outils.

2. Vous serez surpris de la quantité de code que vous pouvez éviter en utilisant des expressions rationnelles avec des principes - dans des "projets pratiques", comme un serveur de messagerie.

3. Si vous êtes majeur en CS, vous allez certainement écrire un compilateur / interprète pour une langue (au moins une petite). Si vous avez déjà essayé cette tâche et êtes bloqué, vous comprendrez à quel point une petite théorie (aussi appelée grammaire sans contexte) peut vous aider. Cette théorie a transformé une tâche jadis impossible en quelque chose qui peut être accompli en un week-end. (Et cela a valu à l'inventeur un prix Turing - google BNF).

4. Si vous êtes majeur en CS, vous devez à un moment donné réfléchir aux fondements philosophiques de l'informatique, et pas seulement à la fraîcheur de la prochaine version de l'API Android. Dans le même ordre d'idées, l'université n'a pas pour tâche de vous préparer aux 5 prochaines années de votre vie, mais de vous préparer aux 50 prochaines années. La seule chose qu'ils peuvent faire à cet égard est de vous aider à penser - penser de la théorie des automates comme l'un de ces cours.

Une des manifestations les plus pratiques de CS est la construction de compilateur. En 1965, Knuth a commencé l’étude des analyseurs syntaxiques de LR. Rapidement (en moins de dix ans), nous avons eu des analyseurs syntaxiques LALR qui sont un sous-ensemble d’automates déterministes qui permettent de mettre en œuvre des analyseurs syntaxiques à décalage / réduction.

Au cœur de la faisabilité et de l'efficacité de l'analyse syntaxique LALR se trouve une preuve (de Knuth) que les "préfixes" de la langue se révèlent être réguliers (votre automate fini). C'est la genèse des générateurs d'analyseurs automatiques tels que yacc / bison, etc.

Il est prudent de dire que les langages de programmation tels que nous les connaissons doivent une grande partie de l'efficacité de leur compilation à ces développements.

Voici un autre exemple: le cœur du protocole TCP / IP est une machine à états finis. Combien plus pratique peut-il obtenir?

Tous les étudiants CS sérieux, en particulier les étudiants pratiques, doivent faire attention à la théorie des automates. C'est la base d'une grande partie de la richesse de l'informatique.

Pouvez-vous entendre ce bruit ? C'est le son de mille brillants théorèmes, applications et outils riant au paradis de la théorie des automates.

Les langues et les automates sont des concepts élégants et robustes que vous trouverez dans tous les domaines de l'informatique. Les langues ne sont pas sèches, les formalistes cèdent la place à la préhistoire informatique. La perspective de la théorie des langues résume des questions apparemment complexes sur des objets opaques sophistiqués en déclarations simples sur des mots et des arbres. Les langages formels jouent un rôle en informatique, à l'instar du point de vue fondamental et novateur apporté par l'algèbre et la topologie aux mathématiques classiques. Voici quelques problèmes pratiques, assez compliqués, qui sont abordés via la théorie des langues.

1. Vous souhaitez repérer les occurrences en double d'une phrase dans un document et supprimer la deuxième occurrence. En substance, vous voulez substituer une séquence dans une langue.
2. Un programme contient-il une violation d'assertion? Un pilote de périphérique respecte-t-il certains protocoles lorsqu’il interagit avec le noyau? Le comportement d'un programme est un ensemble d'exécutions; en d'autres termes, une langue. La propriété correct est une autre langue. Le problème de correction du programme équivaut à une vérification d'inclusion de langue.
3. Votre logiciel peut-il être bloqué dans une boucle infinie? Un algorithme distribué contient-il un livelock? Nous avons besoin de langues sur des mots infinis, mais la vue d'inclusion de langue s'applique toujours.
4. Vous souhaitez créer un désinfectant pour détecter le code Javascript malveillant entré dans une application Web. L'ensemble de chaînes malveillantes est un langage. L'ensemble des chaînes entrées dans les formulaires dans une autre langue. Vous voulez déterminer si l'intersection de ces langues est non vide.
5. Surveillance à l'exécution des systèmes réactifs et critiques. Vous souhaitez concevoir un moniteur logiciel qui supervise le fonctionnement de votre processus chimique ou suivre les mises à jour d'une base de données financières. Ce sont au cœur l'inclusion linguistique et les problèmes d'intersection.
6. Reconnaissance de formes avec ses nombreuses applications. Vous souhaitez détecter des modèles dans les données génomiques, dans le texte, dans une série de rapports de bogues. Ce sont des problèmes où nous recevons des mots d'une langue inconnue et devons deviner la langue. Ce sont des problèmes d'inférence linguistique.
7. Avec un ensemble de documents XML, vous souhaitez procéder au reverse engineering d’un schéma qui s’applique à ces documents. Les documents XML peuvent être idéalisés comme des arbres. Un schéma est alors une spécification d'un langage d'arborescence et le problème d'inférence de schéma est un problème d'inférence de langage sur des langages d'arborescence.
8. De nombreuses applications nécessitent un raisonnement arithmétique automatisé. Supposons que nous fixions une théorie logique telle que l'arithmétique de Presburger, dans laquelle nous avons les nombres naturels, l'addition et le prédicat inférieur à. Une formule à n variables représente un ensemble de vecteurs à n dimensions. Un vecteur est une séquence de chiffres et peut être codé sous forme de mot. Un prédicat est alors un ensemble de mots; une langue. Les opérations logiques telles que la conjonction, la disjonction et la négation deviennent une intersection, une union et un complément des langages (la quantification existentielle est une sorte de projection).

La réduction évoquée ci-dessus considère les langues comme des objets mathématiques abstraits. Pour appliquer ces idées en pratique, nous avons besoin d'une structure de données représentant les langages et des algorithmes permettant de manipuler ces structures de données.

Entrez des automates. Les automates nous permettent de réduire les questions relatives aux objets mathématiques abstraits, comme les langages, à des questions concrètes et algorithmiques sur les graphes étiquetés. Les langages et la théorie des automates, outre un nombre insensé d'applications pratiques, fournissent un service intellectuel très important. Nous pouvons penser aux problèmes allant du formatage des codes postaux aux procédures de décision pour la logique monadique du second ordre dans un espace conceptuel uniforme et dégagé. Comme c'est incroyable!

Je n'ai rien dit sur la logique et les procédures de décision. (Oui, ils ont des applications pratiques.) Voir la réponse de Kaveh pour un aperçu faisant autorité.

Comme cela a été expliqué dans les autres réponses, la théorie des automates est importante sur le plan conceptuel en tant que modèle de calcul simple que nous comprenons bien, et les expressions régulières et les automates ont de nombreuses applications réelles.

Voici un petit exemple de recherche moderne qui remonte à la théorie des automates pour comprendre un concept moderne. Dans cet article, les chercheurs prouvent que les langages normaux ont tous des testeurs de propriétés: "Les langages normaux sont testables avec un nombre constant de requêtes"

Ce ne sont pas que des automates à la vanille. Vous étudiez les bases (états d'acceptation, transitions epsilon, ...) d'un modèle (informatique) qui aide à raisonner sur ce qui peut et, plus important encore, sur ce qui ne peut pas être exprimé avec certains langages de requête. Quelques résultats intéressants incluent:

• oui, le résultat bien connu est que les automates finis déterministes reconnaissent les langages normaux - vous savez donc maintenant ce dont vous avez besoin pour implémenter la correspondance d'expression régulière.
• Les automates Pushdown reconnaissent les grammaires sans contexte - vous avez maintenant une idée de ce à quoi ressemble un analyseur syntaxique (ou du moins une large classe de celles-ci).
• Les automates arborescents reconnaissent les instructions par rapport à la logique monadique de second ordre - vous avez maintenant une idée de ce qu'il faut pour implémenter des langages de programmation par contraintes, ou ... certaines instructions en SQL , par exemple.

(et bien sûr je saute beaucoup d'autres cours)

Fondamentalement, c'est un modèle très général. Vos cours insisteront probablement sur le lien entre automates, langages et logique.

Si je cherchais à associer cela à des outils concrets "mondains", je passerais une matinée à la bibliothèque à lire quelques extraits (AB?) De Foundations of Databases par Abiteboul & al, et à essayer de relier ce document au matériel de la classe. . Bien sûr, ce n’est qu’un des (nombreux) moyens de rechercher des applications d’une classe d’automates, et je suppose que ce n’est pas le plus évident - mais c’est précisément la raison pour laquelle c’est un exercice intéressant.

Comme déjà indiqué dans diverses réponses, la théorie des automates dans les cours d'UG fournit le cadre conceptuel de base permettant d'introduire des sujets plus avancés (et pratiques), ainsi que de mettre en évidence les connexions négligées; par exemple: les diagrammes de décision binaires (ils sont des DFA minimisés; après avoir enseigné le DFA, j'enseigne souvent la résolution de casse-tête basée sur BDD); l'écriture de scripts, y compris dans BioPerl et BioPython (et un excellent paramètre pour renforcer le nombre de correspondances inattendues pouvant être cachées dans les expressions rationnelles de scripts du monde réel), un débogage formel (propriétés d'état telles que FA inversé, intersection) et même la programmation d'alarme par magnétoscope ou intrusion domestique (situation de stress quotidien d'un automate mal spécifié, enseigné à l'aide d'exemples incomplets; peut-être formalisé à l'aide de la synthèse d'interface utilisateur basée sur des scénarios de play-in / play-out de Harel). J'utilise aussi ce paramètre pour enseigner Python '

Je vais donner une autre réponse sous un angle pratique tout à fait différent: les machines à états finis (ou du moins certaines de leurs généralisations / extensions simples) sont souvent utilisées du côté de l'IA de la programmation de jeux. Ils s'avèrent être un excellent modèle pour encapsuler le comportement des personnages. Par exemple, un ennemi peut avoir des états représentant «patrouille», «recherche», «approche», «attaque», «défense», «retraite», «mort», etc., avec des transitions bien définies entre eux. Cela n'implique aucun des aspects formels des automates, comme les langages normaux, etc., mais le concept de l'automate est très fondamental.

Nous avons vu que le langage qui oppose théorie et pratique, plaçant l’un au-dessus de l’autre, est la consommation même de l’ignorance - qu’il prouve à un homme qu’il ne connaît pas les tous premiers éléments de sa pensée et l'esprit d'être assez perverti pour être incapable de leur apprendre.

- James Mill (écrit sous le pseudonyme de «PQ»), «Theory and Practice», The London and Westminster Review , avril 1836

De nombreuses recherches ont été menées sur la théorie des automates dans la vérification de modèles utilisée dans l'industrie. Consultez les récentes conférences de Moshe Vardi au Fields Institute , en particulier la 3ème conférence "Logique, Automates, Jeux et Algorithmes" pour comprendre pourquoi la théorie des automates est toujours aussi importante et utile.

Abstrait:

L'approche des procédures de décision fondée sur la théorie des automates, introduite par Buechi, Elgot, Rabin et Trakhtenbrot dans les années 1950 et 1960, est l'une des approches les plus fondamentales des procédures de décision. Récemment, cette approche a trouvé des applications industrielles dans la vérification formelle de systèmes matériels et logiciels. De la logique aux algorithmes pratiques, le chemin passe non seulement par des automates, mais aussi par des jeux, dont les aspects algorithmiques ont été étudiés par Chandra, Kozen et Stockmeyer à la fin des années 1970. Dans cet exposé général, nous décrivons le chemin qui mène de la logique aux algorithmes via des automates et des jeux.

Les diapositives et les fichiers audio des conférences sont disponibles ici: 1 , 2 , 3 .

Nous devrions prendre en compte la sémantique des mots "pratique" et "application". Pour certains étudiants, la pratique est tout ce qui peut les aider à réussir leurs examens. pour d'autres, tout ce qui va arriver dans un travail. Dans les deux cas, la théorie des automates est très pratique.

Comme d'autres l'ont fait remarquer, vous utiliserez des grammaires, par exemple, pour étudier les compilateurs. Mais plus encore que cela: comprendre tout le concept d’états et de règles différents pour les transitions entre eux peut faire de vous un meilleur programmeur lorsque vous vous rendez compte, par exemple, que votre code est redondant ici et là, et que lorsque vous l’améliorez, sont l' application dans votre code les mêmes idées conceptuelles derrière la minimisation DFA.

De même pour "application". Que comprenez-vous par ce mot? Même si vous êtes un «ingénieur terre-à-terre», vous verrez et utiliserez des idées similaires à celles de la théorie des automates dans des projets réels: code de programmation, diagrammes de flux et même le concept simple mais brillant d'une pile. Pour les nerds de la théorie comme moi, je considère les applications de la théorie des automates dans d'autres domaines, tels que la logique, l'algèbre et la théorie des modèles finis. Certes, je n'aurai probablement jamais besoin d'utiliser le lemme de pompage lors de mes achats dans un supermarché, mais de tels théorèmes m'ont aidé à comprendre la structure de certaines classes de langues, sans oublier les structures de logique et d'algèbre avec lesquelles elles correspondent. Et c’est quelque chose que j’apprécie plus que toute mesure de caractère pratique.

Avec les logiques, les automates peuvent offrir des moyens de vérifier les statemens comme

$\qquad A \models \varphi$

$A$$\varphi$$A$$\varphi$

$\varphi$$A$$\varphi$$A_\varphi$$\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Les automates finis, souvent décrits comme des machines à états finis dans différents contextes, ou avec leurs variantes probabilistes, les modèles de Markov cachés peuvent être appliqués à la reconnaissance de modèle et à la quantification de la structure d'un modèle. Par exemple, quels sont les plus petits automates finis stochastiques qui généreront des chaînes selon, plus ou moins, une distribution de probabilité donnée, ou des propriétés statistiques correspondantes d'un échantillon de chaînes (ou de séries temporelles) à partir d'une distribution.

Voir par exemple CSSR , un algorithme de reconstruction aveugle d'états cachés; il est plus efficace et plus flexible que les modèles de Markov cachés.

Une autre application plus pratique de la théorie des automates est le développement de l'intelligence artificielle. L'intelligence artificielle a été développée à partir du concept d'automate fini. Le réseau neuronal de robots est construit sur la base de la théorie des automates. Après tout, les robots sont aussi des automates.

Certains ont donné d'excellentes réponses quant à la manière dont cela se rapporte à l'industrie. Ce qui devrait être important, c’est sa valeur scientifique, et la théorie des automates est souvent la porte à la compréhension d’un niveau supérieur de la théorie de l’informatique dans les études d’un étudiant de premier cycle. La théorie des automates a un grand ensemble de théorèmes qui apparaissent partout dans l'informatique théorique, et en particulier quand on veut parler d'applications telles que Compilers. Sa valeur scientifique (ce n’est pas dépassé, comment pourrait-il en être? C’est la théorie fondamentale du domaine) est pratique pour tout scientifique qui s’intéresse au calcul. C'est pratique car ce sont des connaissances utiles à ceux qui comprennent ou veulent comprendre la nature du calcul. Si vous ne pouvez pas y trouver une utilité, je remets en question les recherches ou même l’intention d’étudier la CS car ce n’est pas de la programmation