Théorie des automates- une section de mathématiques discrètes qui étudie les automates abstraits - ordinateurs présentés sous forme de modèles mathématiques - et les tâches qu'ils peuvent résoudre.
La théorie des automates est la plus étroitement liée à la théorie des algorithmes : l'automate convertit des informations discrètes par étapes en moments de temps discrets et génère le résultat par étapes d'un algorithme donné.
- 1 Terminologie
- 2 Candidature
- 2.1 Tâches typiques
- 3 Voir aussi
- 4 Littérature
- 5 Liens
Terminologie
symbole- tout bloc atomique de données pouvant avoir un effet sur la machine. Le plus souvent, un symbole est une lettre dans une langue courante, mais il peut s'agir, par exemple, d'un élément graphique d'un schéma.
- Mot- une chaîne de caractères créée par concaténation (connexion).
- Alphabet- un ensemble fini de caractères différents (de nombreux caractères)
- Langue- l'ensemble des mots formés par les symboles de l'alphabet donné. Peut être fini ou infini.
Automates
Les automates peuvent être déterministes ou non déterministes.
Automate fini déterministe (DFA)- est une fonction de transition telle que
- - Etat initial
- - ensemble d'états de l'automate
- - l'alphabet de la langue que l'automate comprend
- est la relation de transition, où est un mot vide. Autrement dit, NFA peut sauter de l'état q à l'état p, contrairement à DFA, à travers un mot vide, et également passer de q à plusieurs états (ce qui est encore une fois impossible dans DFA)
- - ensemble d'états initiaux
- - ensemble d'états finaux.
Un langage L est dit lu (accepté) par un automate M s'il est constitué de mots w basés sur l'alphabet tel que si ces mots sont entrés dans M, en fin de traitement il passe dans l'un des états d'acceptation F :
En règle générale, l'automate passe d'un état à l'autre à l'aide d'une fonction de transition, tout en lisant un caractère à partir de l'entrée. Il existe des automates qui peuvent passer à un nouvel état sans lire un caractère. La fonction de transition sans lecture de caractère est appelée -jump (epsilon-jump).
Application
La théorie des automates sous-tend toutes les technologies numériques et les logiciels, par exemple, un ordinateur est un cas particulier de la mise en œuvre pratique d'une machine à états finis.
Une partie de l'appareil mathématique de la théorie des automates est directement utilisée dans le développement de lexers et d'analyseurs pour les langages formels, y compris les langages de programmation, ainsi que dans la construction de compilateurs et le développement des langages de programmation eux-mêmes.
Une autre application importante de la théorie des automates est la détermination mathématiquement rigoureuse de la solvabilité et de la complexité des problèmes.
Tâches typiques
- Construction et minimisation d'automates- construction d'un automate abstrait à partir d'une classe donnée qui résout un problème donné (acceptant un langage donné), éventuellement avec minimisation ultérieure en termes de nombre d'états ou de nombre de transitions.
- Synthèse d'automates- construire un système d'"automates élémentaires" donnés, équivalent à un automate donné. Un tel automate est dit structurel. Il est utilisé, par exemple, dans la synthèse de circuits électriques numériques sur une base élémentaire donnée.
voir également
- Lemme de la pompe
- Automate abstrait
- Jeu "La vie"
- Forme minimale d'automate
- Théorème de Shannon-Lupanov
Littérature
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction à la théorie des automates, aux langages et au calcul. - M. : Williams, 2002. - S. 528. - ISBN 0-201-44124-1.
- Kasyanov VN Conférences sur la théorie des langages formels, des automates et de la complexité computationnelle. - Novossibirsk : NSU, 1995. - C. 112.
Liens
- Application de la théorie des automates
théorie des automates
Une section de cybernétique théorique qui étudie les modèles mathématiques (appelés automates, machines) de dispositifs réellement existants (techniques, biologiques, etc.) ou fondamentalement possibles qui traitent des informations discrètes à des intervalles de temps discrets. Et. t. se pose hl. façon sous l'influence des exigences de la technologie des ordinateurs numériques et des machines de contrôle, ainsi que des besoins internes de la théorie des algorithmes et de la logique mathématique. Le concept d'« automate » varie sensiblement selon la nature de ces dispositifs, le niveau d'abstraction accepté et le degré de généralité approprié (les automates sont finis, infinis, croissants, probabilistes, déterministes, autonomes, etc.).
La question porte sur le développement d'un tel concept "d'automatique", qui aurait un max. degré de généralité et, en même temps, pourrait servir de base pour poser et résoudre des problèmes suffisamment significatifs, ne peuvent pas être considérés comme encore complètement résolus. Cependant, il peut être considéré comme cas particulier concept général d'un système de contrôle.
Le terme "A. T." est entré en vigueur dans les années 50 du XXe siècle, bien que les problèmes correspondants aient en grande partie commencé à prendre forme dès les années 30 dans le cadre de la théorie des algorithmes et de la théorie des dispositifs de relais. Même alors, les algorithmes de la théorie étaient suffisamment formulés concepts généraux Calcul. automate (voir Machine de Turing) et (implicitement) le concept d'automate fini (tête de machine de Turing). Il a été constaté que pour
toutes sortes de transformations efficaces de l'information, il n'est pas du tout nécessaire de construire à chaque fois des automates spécialisés ; en principe, tout cela peut être fait sur une machine universelle avec le bon programme et le bon codage. Cette théor. le résultat a ensuite reçu une incarnation technique sous la forme d'ordinateurs universels modernes. Machines. Cependant, une étude détaillée des processus se produisant dans les automates de divers types, et des lois générales auxquelles ils sont soumis, n'a commencé plus tard que dans le cadre de A. T. La différence de formulations entre les problèmes de la théorie des algorithmes et A. T. ce que les machines peuvent font et comment ils le font. Puisque l'implication d'autres types d'automates (autres que les machines de Turing) n'augmente certainement pas le stock de transformations calculables de l'information, alors pour la théorie des algorithmes une telle implication n'est qu'épisodique et n'est associée qu'à la technique de preuve appliquée. En revanche, pour A. t., cette considération devient une fin en soi. Théor. et problèmes appliqués d'automatisation, informatique. technologie et programmation, modélisation biologique. comportement, etc., continuent de stimuler les problèmes de A. t. Cependant, parallèlement à cela, A. t. développe déjà ses propres problèmes internes. L'appareil de l'algèbre, de la logique mathématique, de l'analyse combinatoire (y compris la théorie des graphes) et de la théorie des probabilités est largement utilisé dans la théorie algébrique.
Dans la théorie des automates, certaines de ses directions ressortent assez clairement, déterminées par le choix des types d'automates étudiés (finis, probabilistes, etc.), par le niveau d'abstraction accepté (voir Théorie abstraite des automates, Théorie structurale des automates ), ou par les spécificités des mathématiques appliquées. méthodes (voir la théorie des automates algébriques). Parallèlement à cela, des problèmes et des méthodes connexes sont développés de manière intensive dans la théorie des dispositifs de relais, dans la théorie des ordinateurs numériques et dans la théorie de la programmation ; par conséquent, il est souvent difficile de faire la distinction entre les sphères d'action de ces théories et A .t.
Comportement et structure. Au cœur de A. t. sont exactement mat. des concepts qui formalisent des idées intuitives sur le fonctionnement et le comportement de l'automate, ainsi que sur sa structure (structure interne). Du point de vue de leur comportement, les automates sont le plus souvent considérés comme des convertisseurs d'informations de dictionnaire, c'est-à-dire des convertisseurs de suites de lettres en suites de lettres. La transformation mise en œuvre est généralement interprétée comme le calcul des valeurs d'une certaine fonction (opérateur) par les valeurs données des arguments, ou comme la transformation d'enregistrements des conditions de problèmes d'un certain type en enregistrements de les solutions correspondantes. En particulier, le soi-disant. reconnaître les automates, percevoir les informations d'entrée, y réagir de telle manière qu'ils acceptent certaines séquences de signaux d'entrée et en rejettent d'autres. En ce sens, ils reconnaissent ou, comme ils disent, ils représentent de nombreuses séquences d'entrée. Enfin, l'automate génératif fonctionne comme un système autonome, non lié aux informations d'entrée, son comportement est déterminé par les séquences de sortie qu'il est capable de générer. La classification ci-dessus en termes de transformation, de reconnaissance et de génération dépend des règles de fonctionnement de l'automate, c'est-à-dire du programme d'interaction de ses états internes avec l'entrée (provenant de l'environnement externe) et la sortie (produite dans l'automate). environnement externe) signaux. Soient respectivement Q, X, Y l'ensemble des états internes des signaux d'entrée et de sortie de l'automate. S'il s'agit d'un automate déterministe, son programme est formalisé en fonction de la transition f-ts et de la sortie f-ts Ф, indiquant pour chaque signal d'entrée x et chaque état l'état dans lequel passe l'automate, et le signal de sortie généré par celui-ci
La théorie automatique abstraite se caractérise par un niveau d'abstraction plus élevé: le concept d'automate y est identifié avec le concept de programme d'automate, c'est-à-dire avec les cinq (), avec une abstraction complète de sa structure. La structure d'un automate reflète la façon dont il est organisé à partir de composants interactifs plus simples (automates élémentaires ou simplement - éléments), correctement connectés dans système unique. Par exemple, le calcul la machine est composée de cellules élémentaires telles que déclencheurs, onduleurs, etc. ; système nerveux construit à partir de neurones. La classification structurelle des automates est déterminée par la nature des connexions autorisées (les connexions peuvent être rigides ou changer en cours de fonctionnement, soumises à certaines restrictions géométriques), ainsi que les spécificités du fonctionnement et de l'interaction des éléments utilisés ( par exemple, les éléments ne peuvent qu'échanger des informations ou ils peuvent générer de nouveaux éléments, construisant la structure). La formalisation des concepts structuraux s'effectue en termes de différents types de schémas (voir Réseau logique). AN Kolmogorov a décrit une approche qui a conduit à la formulation d'un concept très général, mais toujours constructif, de la structure d'un automate (voir Automates en croissance), qui, apparemment, couvre tous les types connus de structures d'automates et tous ceux qui peuvent être prévus à la science de niveau moderne. Il est bien évident qu'il existe une relation étroite entre la structure d'un automate et son comportement. Cependant, une étude séparée de chacun de ces deux aspects, avec une abstraction significative de l'autre, est non seulement possible, mais souvent utile pour poser et résoudre de nombreux problèmes importants. Une telle étude est menée respectivement dans la théorie abstraite (comportementale) et structurelle des automates.
Types d'appareils. La plus courante est la classification des automates et co-resp. sections d'A. t., consacrées à divers
types de machines, selon les caractéristiques suivantes.
1) La quantité de mémoire. Les automates finis et infinis sont caractérisés selon. finitude et infinité de la quantité de mémoire (le nombre d'états internes). Les automates finis sont des blocs distincts de l'informatique moderne. machines et même la machine dans son ensemble. Le cerveau peut également être considéré comme une machine à états finis. Les automates infinis sont un tapis naturel. une idéalisation qui découle de l'idée d'un automate avec un nombre fini mais infiniment grand d'états. Cela ne fait référence qu'à l'infinité potentielle de la mémoire, qui se manifeste dans le fait que la mémoire, bien qu'elle reste finie à chaque instant du temps, peut croître indéfiniment. Une telle idéalisation est apparue pour la première fois dans le cadre de la théorie des algorithmes lors du processus d'affinement de l'idée intuitive d'un algorithme. Un automate à croissance structurelle est représenté comme une combinaison d'éléments capables de reproduction et de croissance de schéma. Les ordinateurs modernes peuvent être considérés comme des automates croissants (et en même temps potentiellement infinis) dans le sens suivant : pour que les calculs soient complets dans tous les cas, il faut admettre la possibilité d'une croissance illimitée de la mémoire externe (sur bande).
2) Mécanisme de sélection aléatoire. Dans les automates déterministes, le comportement et la structure à chaque instant du temps sont déterminés de manière unique par les informations d'entrée actuelles et l'état de l'automate qui a pris forme à l'instant immédiatement précédent. Dans les automates probabilistes (stochastiques), ils dépendent également d'un choix aléatoire. Les automates stochastiques ne doivent pas être confondus avec les automates non déterministes, dans lesquels la condition d'unicité est également violée (cependant, sans la participation du mécanisme de sélection aléatoire c.l.).
Problèmes et méthodes. Les problèmes centraux de la théorie automatique comprennent les problèmes d'analyse, c'est-à-dire la description du comportement d'un automate en fonction de son programme ou de sa structure donnée, et la synthèse, c'est-à-dire la conception d'automates dont le comportement satisferait à des exigences prédéterminées. Etroitement liés à ces problèmes, il existe de nombreux autres problèmes qui font l'objet d'études approfondies (complétude et universalité, minimisation, langages, estimations asymptotiques, etc.). Surtout, l'analyse et la synthèse ont été étudiées dans la théorie des automates déterministes finis, et elles sont interprétées différemment dans l'abstrait et dans la théorie structurelle des automates. Ainsi, par exemple, en théorie structurelle, la synthèse (voir Synthèse structurelle des automates) signifie la construction d'un circuit à partir d'un assortiment donné d'éléments qui serait optimal. (ou proche de l'optimal) au sens d'un certain critère de complexité des circuits. Les méthodes combinatoires-informationnelles et les estimations asymptotiques prévalent ici (K. Shannon, S. V. Yablonskii, O. B. Lupanov et autres). Dans la théorie abstraite des automates, on se contente de construire un programme de fonctionnement d'un automate (voir Synthèse abstraite des automates), par exemple, sous la forme de fonctions de transition et de sortie pour un automate fini, qui sert généralement de base de départ. matériau pour le développement ultérieur de la synthèse structurale. Ici, principalement algébrique (S. K. Klini, V. M. Glushkov, etc.), mathématique et logique. (B. A. Trakhtenbrot, R. Buchi, etc.) et méthodes et concepts de jeu (R. McNotop). Le problème de l'analyse et de la synthèse des automates déterministes finis occupe également une place prépondérante dans la théorie des dispositifs à relais.
Dans la théorie des expériences avec des automates (E. Moore), des méthodes sont développées qui permettent, à partir d'informations obtenues à partir d'observations externes du comportement d'un automate, de restituer le programme de son fonctionnement, ou du moins certaines de ses propriétés. Ces méthodes peuvent être considérées comme une sorte de synthèse abstraite et de décodage d'automates (Ya. M. Barzdin). Les travaux de K. Shannon, M. Rabin et d'autres ont donné une impulsion au développement de la théorie des automates probabilistes dans les directions suivantes: 1) dans quelle mesure les concepts et méthodes de la théorie des automates déterministes sont transférés aux automates stochastiques ; 2) quelles simplifications du calcul. Les processus sont réalisables en laissant une classe plus étroite d'automates déterministes dans une classe plus large d'automates probabilistes. L'étude des automates en croissance est principalement axée sur les problèmes suivants : 1) le développement de modèles d'automates en croissance et l'étude de leurs classes individuelles (automates itératifs - F. Henny, automates à registre - VM Glushkov, automates auto-reproducteurs - J. von Neumann, automates à croissance généralisée - A. N. Kolmogorov, Ya. M. Barzdin); 2) évaluation de la valeur calculée la capacité et la complexité du calcul des automates en croissance (Ya. M. Barzdin, B. A. Trakhtenbrot, Yu. Khartmanis, G. S. Tseitin, M. Rabin, etc.).
Relation avec d'autres domaines scientifiques.
L'importance de la théorie des algorithmes et de la théorie des dispositifs de relais pour la technologie automatique a déjà été expliquée ci-dessus. Soulignons également la réciprocité d'A. t., dont les méthodes ont permis de résoudre un certain nombre de problèmes qui se posaient en mathématiques. logique et théorie des algorithmes (R. Buchi). La problématique émergente dans la théorie des automates croissants (par exemple, la complexité computationnelle) se situe essentiellement à l'intersection de la théorie des algorithmes et des régularités asymptotiques dans la synthèse structurale des automates. La forte pénétration mutuelle de la linguistique mathématique et de la linguistique mathématique, dont l'un des concepts importants est la grammaire générative, est un objet très proche d'un automate génératif. Ainsi, certaines propositions assez importantes de la théorie des grammaires peuvent, en principe, être attribuées à la théorie automatique : dans la théorie abstraite des automates, mat. les problèmes d'apprentissage, ainsi que le comportement opportun d'un individu ou d'une équipe, ont été clarifiés et étudiés en termes d'automates de jeu (M. L. Tsetlin). Utile
il y avait aussi un lien entre la théorie des automates finis et la théorie de la conception informatique et la théorie de la programmation (V. M. Glushkov, A. A. Letichevsky).
Lit.: Gavrilov M A. Théorie des circuits de contact relais. M.-L., 1950 [bibliogr. à partir de. 298-299] ; « Actes de l'Institut de Mathématiques. Académie des sciences V. A. Steklov de l'URSS, 1958, v. 51; Glushkov V. M. Synthèse d'automates numériques. M., 1962 [bibliogr. à partir de. 464-469] ; Kobrinsky N. E., Trakhtenbrot B. A. Introduction à la théorie des automates finis. M., 1962 [bibliogr. à partir de. 399-402] ; Tsetlin ML Recherche sur la théorie des automates et la modélisation des systèmes biologiques. M., 1969 [bibliogr. à partir de. 306-316] ; Trakhtenbrot B. A., Barzdin Ya. M. Automates finis (Comportement et synthèse). M., 1970 [bibliogr. à partir de. 389-395] ; Automates. Par. de l'anglais. M., 1956. B.A., Trakhtenbrot.
Université d'État de Viatka
FACULTÉ D'AUTOMATIQUE ET GÉNIE INFORMATIQUE
Département des ordinateurs électroniques
Notes de cours sur la théorie des automates (première partie)
Théorie des automates (partie I). Notes de cours /Kirov, Vyatsky Université d'État, 2010, 56s.
Les notes de cours du cours "Théorie des automates" (Partie I) fournissent le matériel théorique nécessaire, y compris les bases de la théorie appliquée des automates numériques, les définitions et règles de base pour la synthèse d'automates finis abstraits, le circuit d'un système discret convertisseur VM Glushkov et trois principaux modèles d'automates finis : le modèle de Mealy, le modèle de Moore et le modèle C-automate. Ensuite, nous considérons des méthodes pour coder des éléments de mémoire, minimiser les automates avec de la mémoire, et une méthode canonique pour synthétiser des automates structurels. Une attention particulière est portée aux règles de construction d'un schéma combinatoire optimal d'un automate selon les équations canoniques, en tenant compte des éléments de mémoire sélectionnés. La littérature pertinente est indiquée.
Le cours magistral est destiné aux étudiants à temps plein de la spécialité 230101 - "Ordinateurs, complexes, systèmes et réseaux", ainsi qu'aux bacheliers de la direction 230100.62 - "Informatique et technologie informatique".
Compilé par : Ph.D., professeur agrégé du département. Ordinateur V.Yu. Meltsov.
Université d'État de Viatka, 2010
Meltsov V.Yu.
1. Présentation 4
2. Problèmes d'analyse et de synthèse 4
3. Automate de contrôle abstrait 7
4. Synthèse d'automates abstraits 9
5. Machine synchrone 10
6. Machines asynchrones 11
7. Machines Mealy et Moore 12
8. Modes de réglage des automates 14
8.1 Manière tabulaire de spécifier les automates 15
8.2. Réglage de l'automate à l'aide de la colonne 17
8.3. Méthode matricielle de spécification des automates 19
9. Passage de la machine de Mealy à la machine de Moore et vice versa 19
10. Les étapes de la synthèse des automates 23
11. Minimiser le nombre d'états internes d'un automate 26
12. Minimisation d'automates entièrement définis. 27
13. Modèle d'automate combiné (C-automate) 31
14. Synthèse structurale d'automate 32
14.1. Méthode canonique de synthèse structurale d'un automate 32
14.2. Synthèse structurale de l'automate C 35
15. Codage des états des automates 41
15.1. La méthode de codage anti-racing des états des automates 42
15.2. Codage voisin des états des automates 45
15.3. Codage d'états d'automates pour minimiser un circuit combinatoire 47
16. Automates à mémoire élémentaires 50
17. Synthèse d'automates sur PLM et ROM 54
1. Introduction
Ces dernières années, des recherches et des travaux sur la création et l'application de divers systèmes automatiques de traitement de l'information ont été menés avec une grande intensité. De tels systèmes sont généralement mis en œuvre sous la forme de blocs qui forment un système de gestion et de traitement d'informations. Conformément à cela, une nouvelle discipline scientifique est née, appelée "Théorie des systèmes".
L'objectif de la théorie des systèmes est de créer un arsenal d'idées et d'outils qui seraient également utiles aux spécialistes de divers domaines (électrotechnique, mécanique, physique, chimie, sociologie, etc.). Cet objectif est atteint en considérant le système non pas à travers sa structure interne, mais à travers les lois mathématiques qui déterminent son comportement observé. Dans ce cas, l'approche la plus couramment utilisée est appelée méthode de la "boîte noire" (c'est-à-dire une méthode dans laquelle les données d'entrée et les données obtenues à la sortie de la machine sont analysées, tandis que les processus internes ne sont pas pris en compte). Il a été prouvé que tous les systèmes peuvent être caractérisés dans les mêmes termes et analysés à l'aide du même ensemble de règles.
La théorie des automates fait partie intégrante de la théorie des systèmes. Il s'agit de modèles mathématiques destinés à représenter plus ou moins approximativement des phénomènes physiques. L'application du modèle de la théorie des automates n'est pas limitée à un domaine particulier, mais il est possible de résoudre des problèmes dans presque tous les domaines d'étude.