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

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

2. Vous serez surpris de la quantité de codage que vous pouvez éviter en utilisant des expressions régulières de principe – dans des «projets pratiques», comme un e-mail serveur.

3. Si vous « êtes un majeur CS, vous » allez certainement écrire un compilateur / interpréteur pour un (au moins un petit) langage. Si vous « avez déjà essayé cette tâche avant et resté coincé, vous apprécierez à quel point une petite théorie (aka grammaires sans contexte) peut vous aider. Cette théorie a transformé une tâche autrefois impossible en quelque chose qui peut être accompli en un week-end. (Et elle a gagné linventeur un prix Turing – google BNF).

4. Si vous « êtes un majeur CS, à un moment donné, vous devez vous asseoir et réfléchir aux fondements philosophiques de linformatique, et non à quel point la prochaine version de lAPI Android est cool. Dans le même ordre didées, cest le travail de luniversité non pas de vous préparer pour les 5 prochaines années de votre vie, mais de vous préparer pour les 50 prochaines. La seule chose quils peuvent faire à cet égard est de vous aider à réfléchir – pensez de la théorie des automates comme lun de ces cours.

Lune des manifestations les plus pratiques de CS est Compiler Construction. En 1965, Knuth a commencé létude des analyseurs LR. Rapidement (en moins dune décennie), nous avons eu des analyseurs LALR qui sont un sous-ensemble dautomates pushdown déterministes qui nous permettent dimplémenter des analyseurs de décalage / réduction.

Au cœur de la faisabilité et de lefficacité de lanalyse LALR se trouve une preuve (par Knuth) que les « préfixes » du langage se révèlent être réguliers (votre automate fini). Cest la genèse des générateurs danalyseurs automatisés comme yacc / bison etc.

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

Voici un autre exemple: le cœur du protocole TCP / IP est une machine à états finis. À quel point cela peut-il être plus pratique?

Chaque étudiant sérieux en CS, en particulier les plus pratiques, devrait prêter attention à la théorie des automates. Cest la base dune grande partie de la richesse de linformatique.

Commentaires

• Lanalyse des fichiers sources nest pas vraiment la partie intéressante (et importante) dun compilateur, donc je ne ‘ Je pense quil est sûr de dire que les  » langages de programmation tels que nous les connaissons doivent une grande partie de leur efficacité de compilation à ces développements « . De plus, il est possible danalyser les langues à laide de différents outils, par exemple des PEG ou des combinateurs danalyse (ie parsec).

Pouvez-vous entendre ce bruit ? Cest le son de mille théorèmes, applications et outils brillants qui rient dans le paradis de la théorie des automates.

Les langages et les automates sont des concepts élégants et robustes que vous retrouverez dans tous les domaines de linformatique. Les langues ne sont pas des relances formelles et sèches de la préhistoire informatique.La perspective de la théorie du langage distille des questions apparemment compliquées sur des objets sophistiqués et opaques en de simples déclarations sur les mots et les arbres. Les langages formels jouent un rôle en informatique semblable au point de vue fondamental et révolutionnaire apporté par lalgèbre et la topologie aux mathématiques classiques. Voici quelques problèmes pratiques, assez compliqués et pratiques qui sont abordés via la théorie du langage.

1. Vous souhaitez repérer les occurrences en double dune phrase dans un document et supprimer la deuxième occurrence. En gros, vous souhaitez remplacer une séquence dans une langue.
2. Un programme contient-il une violation dassertion? Un pilote de périphérique respecte-t-il certains protocoles lorsquil interagit avec le noyau? Le comportement dun programme est un ensemble dexécutions; en dautres termes, une langue. La propriété dexactitude est une autre langue. Le problème de lexactitude du programme équivaut à une vérification dinclusion de langage.
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 dinclusion de langue sapplique toujours.
4. Vous souhaitez créer un désinfectant pour détecter le Javascript malveillant entré dans une application Web. Lensemble des chaînes malveillantes est un langage. Lensemble de chaînes entré dans les formulaires dans une autre langue. Vous souhaitez déterminer si lintersection de ces langages nest pas vide.
5. Suivi dexécution des systèmes réactifs et critiques. Vous souhaitez concevoir un moniteur logiciel qui supervise le fonctionnement de votre procédé chimique ou suivre les mises à jour dune base de données financière. Ce sont au cœur des problèmes dinclusion et dintersection de langage.
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 dune langue inconnue et devons deviner la langue. Ce sont des problèmes dinférence linguistique.
7. Étant donné un ensemble de documents XML, vous souhaitez procéder au reverse engineering dun schéma qui sapplique à ces documents. Les documents XML peuvent être idéalisés dans des arbres. Un schéma est alors une spécification dun langage darbre et le problème dinférence de schéma est un problème dinférence de langage sur des langages darbre.
8. De nombreuses applications nécessitent un raisonnement arithmétique automatisé. Supposons que nous fixions une théorie logique telle que larithmétique de Presburger, dans laquelle nous avons les nombres naturels, laddition et le prédicat inférieur à. Une formule avec 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 lintersection, lunion et le complément des langages (la quantification existentielle est une sorte de projection).

La réduction suggérée ci-dessus traite les langages comme des objets mathématiques abstraits. Pour appliquer ces idées dans la pratique, nous avons besoin dune structure de données pour représenter des langages et des algorithmes pour manipuler ces structures de données.

Entrez les automates. Les automates nous permettent de réduire les questions sur les 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é dapplications pratiques, fournissent un service intellectuel très important. Nous pouvons penser à des 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 épuré. Cest incroyable!

Je nai 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é.

Commentaires

• haha, lironie

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 langues régulières ont toutes des testeurs de propriétés: « Les langues régulières peuvent être testées avec un nombre constant de requêtes »

Ce ne sont pas que des automates à la vanille. Vous apprenez les bases (acceptation des états, epsilon-transitions, …) dun (calcul) modèle qui aide à raisonner sur ce qui peut, et surtout sur ce qui ne peut pas être exprimé avec certains langages de requête. Voici quelques résultats intéressants:

• oui, le célèbre résultat est que Les automates déterministes finis reconnaissent les langues régulières – vous le savez maintenant ce dont vous avez besoin pour implémenter la correspondance dexpressions régulières.
• Les automates déroulants reconnaissent les Grammaires sans contexte – vous avez maintenant une idée de ce à quoi ressemble un analyseur (ou au moins une grande classe de ceux-ci).
• automates darbres reconnaissez les instructions sur la logique monadique du second ordre – vous avez maintenant une idée de ce quil faut pour implémenter certains langages de programmation par contraintes , ou … certaines instructions en SQL , par exemple.

(et bien sûr je « m saute beaucoup des autres classes)

En gros, cest un modèle très général. Vos cours mettront probablement laccent sur le lien entre les automates, les langages et la logique.

Si je cherchais à relier cela à des outils « mondains » concrets, je passerais une matinée tranquille à la bibliothèque à lire quelques parties (AB?) de Fondations des bases de données par Abiteboul & al, et en essayant de relier cela au matériel de classe. Bien sûr, cest juste une des (nombreuses) façons de rechercher des applications dune classe dautomates, et je suppose que ce nest pas la plus évidente – mais cest précisément pourquoi cest un exercice intéressant.

Comme déjà souligné dans diverses réponses, la théorie des automates dans les cours UG donne le cadre conceptuel de base pour introduire des sujets plus avancés (et pratiques), ainsi que pour signaler les connexions négligées; par exemple: les diagrammes de décision binaire (ils sont minimisés DFA; après avoir enseigné DFA, jenseigne souvent la résolution de casse-tête basée sur BDD); des scripts, y compris dans BioPerl et BioPython (et un excellent cadre pour renforcer le nombre de correspondances involontaires pouvant être cachées dans les expressions rationnelles de script du monde réel), le débogage formel (propriétés détat comme FA annulé, intersect), et même la programmation dalarme de magnétoscope ou dintrusion domestique (situation de stress quotidienne dun automate mal spécifié enseignée à travers des exemples incomplets; peut-être formalisée en utilisant la synthèse dinterfaces utilisateur basée sur le scénario play-in / play-out de Harel). Jutilise également le paramètre pour enseigner (presque) purement Python sous-ensemble fonctionnel, y compris les cartes, les lambdas et les compréhensions densembles, à laide desquels on peut coder des algorithmes FA standard, souvent dune manière pratiquement impossible à distinguer des définitions mathématiques.

Commentaires

• Bienvenue, Ganesh!
• Une belle façon denseigner les automates. Seriez-vous prêt à partager vos notes de cours?

De nombreuses recherches ont été menées sur la théorie des automates dans la vérification de modèle utilisée dans lindustrie. Consultez les récentes conférences de Moshe Vardi « au Fields Institute , en particulier la troisième conférence » Logic, Automata, Games, and Algorithms « pour découvrir pourquoi la théorie des automates est toujours important et utile.

Résumé:

Lapproche de la théorie des automates des procédures de décision, introduite par Buechi, Elgot, Rabin et Trakhtenbrot, dans les années 50 et 60, est lune 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 des systèmes matériels et logiciels. à travers les jeux, dont les aspects algorithmiques ont été étudiés par Chandra, Kozen et Stockmeyer à la fin des années 1970. Dans cette présentation, nous décrivons le chemin de la logique aux algorithmes via les automates et les jeux.

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

Je vais lancer une autre réponse sous un angle pratique totalement différent: les machines à états finis (ou au moins quelques généralisations / extensions simples dentre elles) sont souvent utilisées sur lIA côté de la programmation de jeux. Ils savèrent fournir un excellent modèle pour encapsuler le comportement des caractères; 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 nimplique aucun des aspects formels des automates comme les langages réguliers et autres, mais le concept de l’automate est très fondamental.

Nous avons vu que le langage qui oppose théorie et pratique, mettant lune au-dessus de lautre, est la consommation même dignorance – que cela prouve quun homme ne connaît pas les tout premiers éléments de la pensée, et contribue grandement à prouver que son esprit est si perverti quil est incapable de leur apprendre.

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

Nous devons prendre en compte la sémantique des mots «pratique» et «application». Pour certains étudiants, pratique est tout ce qui les aidera à réussir leurs examens; pour dautres, tout ce qui se présentera dans un emploi. Dans les deux cas, la théorie des automates est en effet très pratique.

Comme dautres le soulignent, vous utiliserez des grammaires, par exemple, lors de létude des compilateurs. Mais plus encore: comprendre tout le concept davoir différents états et règles pour les transitions entre eux peut faire de vous un meilleur programmeur lorsque vous réalisez, par exemple, que votre code est redondant ici et là, et que lorsque vous laméliorez, vous appliquent dans votre code les mêmes idées conceptuelles derrière la minimisation DFA.

De même pour « application ». Quentendez-vous par ce mot? Même si vous êtes un « ingénieur terre-à-terre », vous verrez et utiliserez des idées similaires à celles de Automata Theory dans des projets du monde réel: code de programmation, diagrammes de flux et même le concept simple mais brillant dune pile. Pour les nerds de la théorie comme moi, je considère les applications de la théorie des automates dans dautres domaines, comme la logique, lalgèbre et la théorie des modèles finis. Sûrement, je n’aurai probablement jamais besoin d’utiliser le lemme de pompage lors de mes achats dans un supermarché, mais des théorèmes comme celui-ci m’ont aidé à comprendre la structure de certaines classes de langages, sans parler des logiques et des structures algébriques avec lesquelles elles correspondent. Et cest quelque chose que japprécie plus que nimporte quelle mesure pratique.

Associés à des logiques, les automates peuvent offrir des moyens de vérifiez les statemens comme

$ \ qquad A \ models \ varphi $

pour un automate $ A $ et une formule $ \ varphi $. Si $ A $ est un modèle de système et $ \ varphi $ une formalisation des propriétés souhaitées, vous obtenez une vérification du système, un problème très pratique avec un nombre croissant dapplications réalisables.

Considérant le côté automate des choses conduit à de bons algorithmes. Par exemple, si $ \ varphi $ est une formule LTL et $ A $ un automate de Büchi (cest-à-dire un automate fini à exécution infinie) vous pouvez traduire $ \ varphi $ à un automate équivalent $ A_ \ varphi $ et vérifiez si $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Automates finis, souvent é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 formes et à la quantification de la structure dun motif. Par exemple. quel est le plus petit automate fini stochastique qui générera des chaînes en fonction, plus ou moins, dune distribution de probabilité donnée, ou des propriétés statistiques correspondantes dun échantillon de chaînes (ou de séries chronologiques) dune certaine distribution.

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

Commentaires

• Pour ajouter au côté pratique, les modèles de Markov cachés sont utilisés dans la reconnaissance vocale des programmes tels que Kurzweil.

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

Certains ont donné dexcellentes réponses en ce qui concerne son rapport avec lindustrie. Ce qui devrait être important, cest sa valeur scientifique, et la théorie des automates est souvent la porte dentrée pour comprendre dabord un niveau supérieur de théorie du calcul dans les études dun étudiant de premier cycle. La théorie des automates a un grand ensemble de théorèmes qui surgissent partout dans linformatique théorique, et surtout quand on veut parler dapplications telles que les compilateurs. Sa valeur scientifique (elle nest pas dépassée, comment pourrait-elle lêtre? Cest la théorie fondamentale du domaine.) Est pratique pour tout scientifique qui sintéresse au calcul. Elle est pratique car ce sont des connaissances utiles à ceux qui comprennent ou veulent pour comprendre la nature du calcul. Si vous ne trouvez pas d’utilité, je remets en question ses recherches ou même l’intention d’étudier la CS car ce n’est pas de la programmation (c’est une application de CS), c’est une science formelle.