Quelle est l'illumination que je suis supposé atteindre après avoir étudié les automates finis?

Je me suis amusé à réviser la théorie du calcul pour le plaisir et cette question me harcelait depuis un moment (drôle, je n'y ai jamais pensé lorsque j'ai appris la théorie des automates à mes études de premier cycle). Alors "pourquoi" étudions-nous exactement les automates finis déterministes et non déterministes (DFA / NFA)? Voici donc quelques réponses que j'ai trouvées après un discours mais que je ne vois toujours pas dans quelle mesure elles ont contribué au moment "aha":

1. Etudier ce qu’ils sont et ne sont pas capables de faire, c’est-à-dire des limitations
   • Pourquoi?
2. Étant donné qu’ils sont les modèles de base du calcul théorique et fonderaient d’autres modèles de calcul plus performants.
   • Qu'est-ce qui les rend "basiques"? Est-ce qu'ils n'ont qu'un seul bit de stockage et de transition d'état?
3. Ok, et alors? Comment tout cela contribue-t-il à répondre à la question de la calculabilité? Il semble que les machines de Turing aident à bien comprendre cela et qu'il existe des modèles de calcul moins complexes, tels que les PDA, les DFA / NFA / Regex, etc.

Donc, même si je «comprends» dans une certaine mesure, je suis incapable de me répondre à cette question? Comment expliqueriez-vous le mieux pourquoi étudier les D / N-FA? Quelle est la question à laquelle ils cherchent à répondre? Comment cela aide-t-il et pourquoi est-ce la première chose enseignée dans la théorie des automates?

PS: Je connais les différentes applications lexicographiques et les simulateurs de motifs qui peuvent être implémentés en tant que tels. Cependant, je ne souhaite pas savoir à quoi il sert dans la pratique mais quelle était la raison de leur utilisation / invention / conception lors de l’aboutissement de l’étude de la théorie du calcul. D'un point de vue historique, qu'est-ce qui a amené quelqu'un à commencer par cela et à quelle compréhension «aha» est-il censé aboutir? Si vous deviez expliquer leur importance aux étudiants CS qui commencent tout juste à étudier la théorie des automates, comment le feriez-vous?

J'ai personnellement apprécié plusieurs Aha! moments de l'étude de la théorie de base des automates. Les NFA et les DFA forment un microcosme pour l'informatique théorique dans son ensemble.

1. Le non-déterminisme mène-t-il à l'efficacité? Il existe des exemples standard dans lesquels l'automate déterministe minimal d'un langage est exponentiellement plus grand qu'un automate non déterministe minimal. Comprendre cette différence pour les machines de Turing est au cœur de l’informatique (théorique). Les NFA et les DFA fournissent l'exemple le plus simple que je connaisse où vous pouvez voir explicitement le fossé qui sépare le déterminisme du non-déterminisme.
2. Computabilité! = Complexité. NFA et DFA représentent tous les deux langues régulières et sont équivalentes à ce qu'ils calculent. Ils diffèrent dans la façon dont ils calculent.
3. Machines Affiner les langues. Ceci est une vision différente de ce que nous calculons et de la façon dont nous calculons. Vous pouvez penser aux langages calculables (et aux fonctions) comme définissant une classe d'équivalence d'automates. Il s’agit d’un changement fondamental de perspective dans TCS, dans lequel nous ne nous concentrons pas uniquement sur le quoi, mais sur le mode de calcul, et nous essayons de choisir le bon «comment» lors de la conception d’un algorithme ou de comprendre l’espace des différentes méthodes d’étude des classes de complexité.
4. La valeur de la représentation canonique. Les DFA sont l'exemple par excellence d'une structure de données admettant une représentation canonique. Chaque langue standard a un DFA unique et minimal. Cela signifie que, avec un minimum de DFA, des opérations importantes telles que l'inclusion de la langue, la complémentation et la vérification de l'acceptation d'un mot deviennent triviales. Concevoir et exploiter des représentations canoniques est une astuce utile lors du développement d'algorithmes.
5. L'absence de représentations canoniques. Il n’existe pas de représentation canonique bien acceptée des expressions régulières ou de NFA. Ainsi, malgré le point ci-dessus, les représentations canoniques n'existent pas toujours. Vous verrez cela dans de nombreux domaines de l’informatique. (Par exemple, les formules de logique propositionnelle n'ont pas non plus de représentations canoniques, contrairement aux ROBDD).
6. Le coût d'une représentation canonique. Vous pouvez même comprendre la différence entre les NFA et les DFA en tant que théorème algorithmique sans déjeuner libre . Si nous voulons vérifier l'inclusion de la langue entre, ou compléter une NFA, vous pouvez la déterminer, la minimiser et continuer à partir de là. Cependant, cette opération de "réduction" a un coût. Vous verrez des exemples de canonisation coûteuse dans plusieurs autres domaines de l'informatique.
7. Infini! = Indécidable. Une idée fausse commune est que les problèmes de nature infinitaire sont intrinsèquement indécidables. Les langages normaux contiennent une infinité de chaînes et possèdent plusieurs propriétés décidables. La théorie des langages réguliers vous montre que l'infini seul n'est pas la source de l'indécidabilité.
8. Tenir l'infini dans la paume de votre automate. Vous pouvez voir un automate fini uniquement comme une structure de données permettant de représenter des ensembles infinis. Un ROBDD est une structure de données permettant de représenter des fonctions booléennes, que vous pouvez comprendre comme représentant des ensembles finis. Un automate fini est une extension naturelle et infinitaire d'un ROBDD.
9. L'humble processeur. Un processeur moderne en contient beaucoup, mais vous pouvez le comprendre comme un automate fini. Cette réalisation a rendu l’architecture des ordinateurs et la conception des processeurs beaucoup moins intimidantes pour moi. Cela montre aussi que, dans la pratique, si vous structurez et manipulez vos états avec précaution, vous pouvez aller très loin avec des automates finis.
10. La perspective algébrique. Les langages ordinaires forment un monoïde syntaxique et peuvent être étudiés sous cet angle. Plus généralement, vous pourrez également vous demander, dans des études ultérieures, quelle est la bonne structure algébrique correspondant à un problème de calcul.
11. La perspective combinatoire. Un automate fini est un graphe étiqueté. Vérifier si un mot est accepté revient à trouver un chemin dans un graphe étiqueté. Les algorithmes d'automates équivalent à des transformations de graphes. Comprendre la structure des automates pour diverses sous-familles de langages réguliers est un domaine de recherche actif.
12. Le triangle amoureux algèbre-langage-combinatoire. Le théorème de Myhill-Nerode vous permet de commencer par un langage et de générer un automate ou un monoïde syntaxique. Mathématiquement, nous obtenons une traduction entre des types d'objets mathématiques très différents. Il est utile de garder à l’esprit ces traductions, de les rechercher dans d’autres domaines de l’informatique et de les parcourir en fonction de votre application.
13. Les mathématiques sont le langage des grandes images. Les langages normaux peuvent être caractérisés par des NFA (graphes), des expressions régulières (grammaire formelle), des machines de Turing en lecture seule (machine), des monoïdes syntaxiques (algèbre), des algèbres de Kleene (algèbre), la logique monadique de second ordre, etc. Le phénomène est que les concepts importants et durables ont de nombreuses caractérisations mathématiques différentes, chacune apportant des saveurs différentes à notre compréhension de l’idée.
14. Lemmas pour le mathématicien actif. Le Lemma de pompage est un excellent exemple d’outil théorique que vous pouvez utiliser pour résoudre différents problèmes. Travailler avec Lemmas est une bonne pratique pour essayer de tirer parti des résultats existants.
15. Nécessaire! = Suffisant. Le théorème de Myhill-Nerode vous donne les conditions nécessaires et suffisantes pour qu'une langue soit régulière. La lemme de pompage nous donne les conditions nécessaires. Comparer les deux et les utiliser dans différentes situations m'a aidé à comprendre la différence entre les conditions nécessaires et suffisantes dans la pratique mathématique. J'ai aussi appris qu'une condition nécessaire et suffisante réutilisable est un luxe.
16. La perspective du langage de programmation. Les expressions régulières sont un exemple simple et beau de langage de programmation. En concaténation, vous avez un analogue de composition séquentielle et en Kleene étoile, vous avez l'analogue d'itération. En définissant la syntaxe et la sémantique des expressions régulières, vous faites un pas en avant dans la direction de la théorie des langages de programmation en utilisant des définitions inductives et une sémantique compositionnelle.
17. La perspective du compilateur. La traduction d'une expression régulière en un automate fini est également un compilateur théorique simple. Vous pouvez voir la différence entre l'analyse, la génération de code intermédiaire et les optimisations du compilateur, en raison de la différence entre la lecture d'une expression régulière, la génération d'un automate, puis la minimisation / détermination de l'automate.
18. Le pouvoir de l'itération. En voyant ce que vous pouvez faire dans un automate fini avec ou sans boucle, vous pouvez apprécier le pouvoir de l'itération. Cela peut aider à comprendre les différences entre les circuits et les machines, ou entre la logique classique et la logique à point fixe.
19. Algèbre et Coalgebra. Les langues ordinaires forment un monoïde syntaxique, qui est une structure algébrique. Les automates finis forment ce que dans le langage de la théorie des catégories on appelle un charbon. Dans le cas d'un automate déterministe, on peut facilement basculer entre une représentation algébrique et une représentation coalgébrique, mais dans le cas des NFA, ce n'est pas si facile.
20. La perspective arithmétique. Il existe un lien profond entre le calcul et la théorie des nombres. Vous pouvez choisir de comprendre cela comme une déclaration sur le pouvoir de la théorie des nombres et / ou l'universalité du calcul. Vous savez généralement que les automates finis peuvent reconnaître un nombre pair de symboles et qu’ils ne peuvent pas compter assez pour correspondre à la parenthèse. Mais de combien d'arithmétique sont-ils capables? Les automates finis peuvent décider des formules arithmétiques de Presburger. La procédure de décision la plus simple que je connaisse pour l'arithmétique de Presburger réduit une formule à un automate. C’est un aperçu de la progression du dixième problème de Hilbert et de sa résolution qui a permis de découvrir une connexion entre les équations de Diophantine et les machines de Turing.
21. La perspective logique. Le calcul peut être compris d'un point de vue purement logique. Les automates finis peuvent être caractérisés par une logique faible, monadique du second ordre, sur des mots finis. Ceci est mon exemple favori non trivial de caractérisation logique d’un dispositif informatique. La théorie descriptive de la complexité montre que de nombreuses classes de complexité ont également des caractérisations purement logiques.
22. Des automates finis se cachent dans des endroits que vous n'avez jamais imaginés. (Chapeau au commentaire de Martin Berger sur le lien avec la théorie de codage) Le prix Nobel de chimie 2011 a été attribué à la découverte de quasi-cristaux. Les mathématiques derrière les quasi-cristaux sont liées aux pavages apériodiques. Un pavage apériodique spécifique de l'avion s'appelle le pavage à la roue, qui consiste en une forme de cerf-volant et une forme de nœud papillon. Vous pouvez coder ces formes en termes de 0 et de 1, puis étudier les propriétés de ces séquences, qui codent des séquences de modèles. En fait, si vous mappez 0 à 01 et 1 à 0 et appliquez de manière répétée cette carte au chiffre 0, vous obtiendrez 0, 01, 010, 01001, etc. Notez que les longueurs de ces chaînes suivent la séquence de Fibonacci. Les mots générés de cette manière sont appelés mots de Fibonacci. Certaines séquences de formes observées dans les pavages de Penrose peuvent être codées comme des mots de Fibonacci. Ces mots ont été étudiés dans une perspective de théorie automatique, et devinez quoi, certaines familles de mots sont acceptées par des automates finis et fournissent même des exemples de comportement dans le pire des cas pour des algorithmes standard tels que l'algorithme de minimisation de Hopcroft. S'il te plaît, dis-moi que tu as le vertige.

Je pourrais continuer (et ainsi de suite) * Je trouve utile d’avoir des automates derrière la tête et de les rappeler de temps en temps pour comprendre un nouveau concept ou pour acquérir une intuition à propos d’idées mathématiques de haut niveau. Je doute que tout ce que je viens de mentionner puisse être communiqué dans les premières conférences d’un cours, voire dans un premier cours. Ce sont des récompenses à long terme basées sur un investissement initial dans les conférences initiales d'un cours de théorie des automates.

Pour parler de votre titre: je ne cherche pas toujours l'illumination, mais quand je le fais, je préfère les automates finis. Reste soif, mon ami.

Il existe de nombreuses bonnes raisons théoriques d'étudier les N / DFA. Deux qui me viennent immédiatement à l’esprit sont:

1. Les machines Turing (nous pensons) capturent tout ce qui est calculable. Cependant, nous pouvons nous demander: quelles sont les parties essentielles d’une machine de Turing? Que se passe-t-il lorsque vous limitez une machine de Turing de différentes manières? Les DFA constituent une limitation très grave et naturelle (perte de mémoire). Les PDA sont une limitation moins sévère, etc. Il est théoriquement intéressant de voir ce que la mémoire vous donne et ce qui se passe lorsque vous vous en privez. Cela me semble une question très naturelle et fondamentale.

2. Les machines de Turing ont besoin d'une bande infinie. Notre univers est fini, donc, dans un certain sens, chaque périphérique informatique est un DFA. Cela semble être un sujet important, et encore naturel, à étudier.

Demander pourquoi on devrait étudier les DFA équivaut à se demander pourquoi on devrait apprendre le théorème de complétude de Godel alors que la vraie chose intéressante est son théorème d' incomplétude .

La raison pour laquelle ils sont le premier sujet de la théorie des automates est qu’il est naturel de passer de modes moins compliqués à des modes moins compliqués.

Pour ajouter une perspective supplémentaire au reste des réponses: parce que vous pouvez réellement faire des choses avec des automates finis, contrairement aux machines de Turing.

Toutes les propriétés intéressantes des machines de Turing sont indécidables. Au contraire, avec les automates finis, à peu près tout est décidable. L'égalité linguistique, l'inclusion, la vacuité et l'universalité sont décidables. Combinées à ces automates finis, toutes les opérations auxquelles vous pouvez penser sont terminées et que ces opérations sont calculables, vous pouvez faire à peu près tout ce que vous voudriez faire avec des automates finis.

Cela signifie que si vous pouvez capturer quelque chose à l'aide d'automates finis, vous disposez automatiquement de nombreux outils pour l'analyser. Par exemple, dans les tests de logiciels, les systèmes et leurs spécifications peuvent être modélisés comme des automates finis. Vous pouvez ensuite tester automatiquement si votre système implémente correctement la spécification.

Les machines de Turing et les automates finis enseignent donc aux gens un contraste intéressant et omniprésent: plus de pouvoir descriptif va de pair avec moins de traçabilité. Les automates finis ne peuvent pas décrire grand chose, mais nous pouvons au moins faire des choses avec eux.

Etat. vous devez apprendre que l'on peut modéliser le monde (pour certains problèmes) comme un espace d'états fini, et que l'on peut penser au calcul dans ces paramètres. Ceci est une idée simple mais extrêmement utile si vous effectuez une programmation - vous rencontreriez des états, encore et encore, et FA vous donnerait le moyen de les penser. Je considère cela comme une excuse suffisante pour enseigner un cours complet. Bien entendu, l'état peut être déterministe ou non déterministe. Ainsi, DFA et NFA, mais vous pouvez convertir entre eux, etc.

La deuxième chose à apprendre est le théorème Halting. Ce qui est lié au théorème d'incomplétude de Godel. (Vous ne pouvez pas construire une machine capable de tout calculer, et il existe des affirmations mathématiques que vous ne pouvez ni prouver ni réfuter, et qui doivent donc être considérées comme des axiomes. C’est-à-dire que nous vivons dans un monde qui n’a pas de description précise ni de réalité. oracles - oui pour nous!)

Maintenant, j'ai fait mes études de premier cycle en maths, et vous vous habituez à l'idée d'apprendre des choses dont vous n'avez aucune idée (l'apprentissage de la théorie des groupes, de la théorie des mesures, de la théorie des ensembles, des espaces de Hilbert, etc., etc., etc.). , BTW]). Il y a quelque chose à dire sur comment apprendre à apprendre - la prochaine fois que vous devrez apprendre quelques mathématiques bizarro (parce que vous devez les utiliser pour faire quelque chose dans le monde réel) qui vous paraît très étrange et que vous prenez dans la foulée. Plus précisément, la troisième chose à apprendre est la maturité mathématique - être capable de bien argumenter, de savoir quand les preuves sont correctes ou non, d'écrire des preuves, etc. Si vous en avez déjà un, ce cours est facile, et vous ne vous en soucierez pas trop. bien pourquoi tu l'apprends.

À part cela, le cours est une perte de temps totale, comme tout le reste. Plus précisément, vous pouvez mener une vie heureuse sans connaître ces informations. Mais ceci est littéralement vrai de toute connaissance. Plus ou moins. Pour moi, un cours à l'université vaut son temps, si vous regardez le monde différemment après l'avoir appris. C’est définitivement l’un des cours qui a changé ma façon de penser le monde. Que peut-on demander de plus?

Bien que ce ne soit pas vraiment la raison pour laquelle ils ont été étudiés à l'origine, les automates finis et les langages normaux qu'ils reconnaissent sont suffisamment flexibles pour être utilisés comme blocs de construction pour des théories mathématiques plus complexes. Dans ce contexte, voir des groupes particulièrement automatiques (groupes dans lesquels les éléments peuvent être représentés par des chaînes dans un langage courant et dans lesquels les produits des éléments par des générateurs de groupe peuvent être calculés par des transducteurs à états finis) et des sous-décalages sofic (sous-décalages d'un espace de décalage dont les mots interdits forment une langue normale). Il y a donc des raisons de les étudier, même si vous êtes intéressé par les mathématiques pures plutôt que par l'informatique.

Des automates finis ont également été utilisés dans la conception d'algorithmes pour d'autres types d'objets. Par exemple, un algorithme de Culik permettant de vérifier si un automate cellulaire unidimensionnel est réversible implique de construire, de modifier et de tester les propriétés de certains NFA. Et un article de FOCS rédigé en 1986 par Natarajan a montré comment résoudre un certain problème dans la conception des chaînes d’assemblage mécanique en le réduisant à un calcul concernant les automates finis.

Vous posez (au moins) deux questions différentes: (a) Quelles parties de la théorie reposent sur des automates finis? (b) Pourquoi les automates finis ont-ils été développés en premier lieu? Je pense que le meilleur moyen de s’attaquer à ce dernier est de regarder les anciens papiers, tels que:

• Rabin, Scott, Automates finis et leurs problèmes de décision , 1959

Voici les deux premiers paragraphes:

Les machines de Turing sont largement considérées comme le prototype abstrait des calculateurs numériques; Cependant, les travailleurs sur le terrain ont de plus en plus l'impression que la notion de machine de Turing est trop générale pour servir de modèle précis d'ordinateurs réels. Il est bien connu que même pour des calculs simples, il est impossible de donner une limite supérieure a priori sur la quantité de bande dont une machine de Turing aura besoin pour un calcul donné. C'est précisément cette caractéristique qui rend le concept de Turing irréaliste.

L'idée d'un automate fini est apparue dans la littérature ces dernières années . Ce sont des machines n'ayant qu'un nombre fini d'états internes pouvant être utilisées pour la mémoire et le calcul. La restriction sur la finitude semble donner une meilleure approximation à l'idée d'une machine physique. Bien sûr, de telles machines ne peuvent pas faire autant que les machines de Turing, mais l’avantage de pouvoir calculer une fonction récursive générale arbitraire est discutable, car très peu de ces fonctions apparaissent dans des applications pratiques.

En bref, ils ont été développés comme un modèle d’ordinateurs réels, dotés de ressources limitées.

Une autre raison est qu’il s’agit de modèles théoriques relativement pratiques . Une machine de Turing, en dehors de l'impossibilité de l'infini bande, est un peu difficile à programmer pour ce que c'est comme de programmer un ordinateur (notez que ce n'est pas une bonne analogie pour commencer!). Les PDA et les DFA sont toutefois tout à fait disposés à être des modèles de programmes réels en ce sens qu’une conception PDA / DFA peut souvent être facilement transformée en un véritable programme. La conception du compilateur, par exemple, les utilise beaucoup. Ainsi, à ce type de points de connexion entre la théorie et la pratique, nous avons une idée de la façon dont tout est lié, et de ce que nous pouvons et ne pouvons pas faire.

Découvrez le jeu "Living Binary Addition" ici: http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html J'avais l'habitude de présenter ce jeu à mes étudiants dans les premiers chapitres sur DFA / NFA. Il illustre deux choses importantes dans la théorie des automates:

1. Comment transformer un processus mental en un simple processus mécanique
2. Qu'est-ce que l'abstraction signifie vraiment. Deux états, comme C et Z ci-dessus, peuvent être n'importe quoi: des transistors dans un ordinateur, un mécanisme hydraulique ou deux joueurs humains!

Cela apporte parfois le moment "Aha" à mes étudiants.

Le concept de DFA est très utile pour concevoir des solutions efficaces à de nombreux types de problèmes. Un exemple est le réseautage. Chaque protocole peut être implémenté comme une machine à états. Implémenter la solution de cette manière rend le code plus simple et plus simple signifie un taux de défauts plus bas. Cela signifie également que les modifications du code sont plus faciles et ont un impact moindre, avec encore moins de taux de défauts.

Certaines personnes ont du mal à considérer un protocole réseau comme une machine à états, mais ceux qui peuvent faire le saut le trouvent très enrichissant en termes de retour sur investissement.

En fait, mes étudiants me demandent parfois précisément cela - après avoir passé une grande partie du semestre sur des automates finis et finalement arriver aux machines de Turing. Pourquoi consacrer autant de temps à un formalisme plus faible alors qu’il existe un formalisme plus fort? J'explique donc le compromis inhérent entre pouvoir expressif et complexité analytique. Les modèles les plus riches sont généralement plus difficiles à analyser. La dichotomie DFA contre TM est extrême, car le problème de l'adhésion est trivial pour l'un et incalculable pour l'autre. Un exemple moins extrême serait DFA vs PDA. Le problème de l’appartenance à ce dernier s’avère être efficacement résolu, mais la solution n’est pas du tout anodine. Nous constatons cet événement dans de nombreuses branches des mathématiques et des sciences: étudiez un modèle simple pour obtenir une compréhension aussi complète que possible, ce qui conduit généralement à mieux comprendre des modèles plus complexes.

Je vois plusieurs réponses appelant FM "moins" que les machines de Turing.

L’un des objectifs principaux de la classe de troisième cycle que j’ai choisie était leur équivalence, et non leurs distinctions. Pour chaque modèle de FSM que nous avons étudié, nous devions prouver leur équivalence à Turing Machines. Ceci est fait en implémentant une machine de Turing dans le FSM. IIRC, nous avons également étudié d’autres modèles informatiques qui ne mettent pas en œuvre une MT, mais j’oublie ce qu’ils étaient. Le fait est que si vous pouvez implémenter une MT, vous pouvez exécuter n’importe quel programme de MT sur le modèle, avec une bande analogique suffisamment grande pour le problème à traiter.

La réponse à la question était la suivante: TM est le modèle de calcul de base, mais il n’est pas très pratique pour construire des machines utiles. D'où les modèles FSM.

Cela m’a été rapporté viscéralement quand, à peu près à la même époque (1984), j’ai découvert le langage FORTH. Son moteur d'exécution repose sur la réalisation pure d'un PDA Dual Stack. En allant plus loin, j'aime ce même moteur sous les compilateurs d'expression

Bien que, pour moi, l’impact réel de FSM ait été de découvrir le livre "Theory of Finite Automata" de Trakhtenbrot et Korzynski (?) Quand j’avais 18 ans, une découverte qui m’a essentiellement permis de faire carrière.