25:
5774:
5784:
5794:
50:
3278:. Some other examples which could be explained using automata theory in biology include mollusk and pine cone growth and pigmentation patterns. Going further, a theory suggesting that the whole universe is computed by some sort of a discrete automaton, is advocated by some scientists. The idea originated in the work of
3306:
Automata simulators are pedagogical tools used to teach, learn and research automata theory. An automata simulator takes as input the description of an automaton and then simulates its working for an arbitrary input string. The description of the automaton can be entered in several ways. An automaton
100:
comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a finite
2391:
Automata are defined to study useful machines under mathematical formalism. So the definition of an automaton is open to variations according to the "real world machine" that we want to model using the automaton. People have studied many variations of automata. The following are some popular
268:
In the 1960s, a body of algebraic results known as "structure theory" or "algebraic decomposition theory" emerged, which dealt with the realization of sequential machines from smaller machines by interconnection. While any finite automaton can be simulated using a
3607:: "The theories, now well developed, of the "finite-state machine" (Gill, 1962), of the "noiseless transducer" (Shannon and Weaver, 1949), of the "state-determined system" (Ashby, 1952), and of the "sequential circuit", are essentially homologous."
6594:
4155:
358:, also according to the previous state and current input symbol. The automaton reads the symbols of the input word and transitions between states until the word is read completely, if it is finite in length, at which point the automaton
1786:
2360:
3311:
or its specification may be entered in a predesigned form or its transition diagram may be drawn by clicking and dragging the mouse. Well known automata simulators include Turing's World, JFLAP, VAS, TAGS and SimStudio.
3460:. Then one can show that such variable automata homomorphisms form a mathematical group. In the case of non-deterministic, or other complex kinds of automata, the latter set of endomorphisms may become, however, a
2574:: An automaton that, after reading an input symbol, may jump into any of a number of states, as licensed by its transition relation. The term transition function is replaced by transition relation: The automaton
468:
1547:
120:
theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the
1615:
2440:
of itself for each successor and each such copy starts running on one of the successor symbols from the state according to the transition relation of the automaton. Such an automaton is called a
2202:
2143:
680:
2876:
The following is an incomplete hierarchy in terms of powers of different types of virtual machines. The hierarchy reflects the nested categories of languages the machines are able to accept.
1140:
3062:
2976:
4147:
Part One: Automata and
Languages, chapters 1–2, pp. 29–122. Section 4.1: Decidable Languages, pp. 152–159. Section 5.1: Undecidable Problems from Language Theory, pp. 172–183.
6539:
109:(represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its
1035:
617:
1848:
1470:
2263:
1357:
934:
797:
216:. With the publication of this volume, "automata theory emerged as a relatively autonomous discipline". The book included Kleene's description of the set of regular events, or
6584:
830:
253:, which gives a necessary and sufficient condition for a formal language to be regular, and an exact count of the number of states in a minimal machine for the language. The
3458:
2643:
cannot have final states, as infinite words never terminate. Rather, acceptance of the word is decided by looking at the infinite sequence of visited states during the run.
6589:
5830:
2672:
Automata theory is a subject matter that studies properties of various types of automata. For example, the following questions are studied about a given type of automata.
2051:
1567:
1067:
861:
4106:
1979:
967:
273:, this requires that the simulating circuit contain loops of arbitrary complexity. Structure theory deals with the "loop-free" realizability of machines. The theory of
1944:
1806:
639:
1924:
1495:
572:
520:
490:
3468:
3025:
3000:
2973:
2945:
1415:
1384:
1302:
1275:
1248:
1221:
1194:
1167:
4436:
3221:
3189:
3157:
3125:
3093:
3059:
2918:
1658:
2222:
2025:
2005:
1888:
1868:
1698:
1678:
1635:
725:
705:
546:
3324:
of automata following the automata classification into different types described in the previous section. The mathematical category of deterministic automata,
289:
to one viewed as acting in discrete time-steps, with its state behavior and outputs defined at each step by unchanging functions of only its state and input.
6208:
2857:
6577:
6213:
4325:
3325:
2658:
2701:
Is it possible to transform a given non-deterministic automaton into a deterministic automaton without changing the language recognized? (Determinization)
3472:
4329:
1703:
2686:
How expressive is a type of automata in terms of recognizing a class of formal languages? And, their relative expressive power? (Language hierarchy)
2271:
5823:
2450: : The two extensions above can be combined, so the automaton reads a tree structure with (in)finite branches. Such an automaton is called an
3294:
that can be written as composition of degree two polynomials is in fact a regular language. Another problem for which automata can be used is the
5937:
6572:
3224:
6390:
4756:
3561:
3966:
417:
29:
5816:
4429:
105:(FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of
28:
6435:
4810:
4051:
James
Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North American Annual Meeting, 17 March 2010
277:
also took shape in the 1960s. By the end of the decade, automata theory came to be seen as "the pure mathematics of computer science".
2612:: Automata may read their input from left to right, or they may be allowed to move back-and-forth on the input, in a way similar to a
4130:
161:, studying the behavior of discrete-parameter systems. Early work in automata theory differed from previous work on systems by using
1500:
30:
5942:
6351:
3767:
3706:
61:, and changes states following the arrows marked 0 or 1 according to the input symbols as they arrive. The double circle marks S
5527:
5499:
4643:
4422:
2404:: An automaton that accepts only finite sequences of symbols. The above introductory definition only encompasses finite words.
5952:
5552:
4388:
4353:
4307:
4226:
4195:
4165:
4140:
4116:
4033:
3909:
1572:
394:
381:. Then, depending on whether a run starting from the starting state ends in an accepting state, the automaton can be said to
6518:
5403:
4568:
5972:
5967:
5557:
4829:
4658:
2750:
2152:
2073:
647:
254:
32:
31:
5062:
4583:
3255:
1076:
2562:: For a given current state and an input symbol, if an automaton can only jump to one and only one state then it is a
5709:
5537:
5067:
4282:
3544:
2922:
350:
that takes the previous state and current input symbol as parameters. At the same time, another function called the
6385:
6069:
5797:
4891:
4751:
4736:
3028:
2949:
2744:
972:
584:
69:
to itself contain an even number of arrows marked 0, this automaton accepts strings containing even numbers of 0s.
6643:
6132:
5892:
5185:
4612:
3308:
3128:
2788:
1811:
6059:
5476:
5438:
5095:
4803:
3295:
2887:
234:
125:, which describes a nesting relationship between major classes of automata. Automata play a major role in the
6064:
5957:
5618:
5595:
5325:
5315:
4780:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
3800:
3488:
3413:
1420:
2235:
1307:
6618:
5962:
5699:
5287:
5195:
5100:
4876:
4861:
4629:
4554:
3727:
3160:
3096:
2491:
number of states. Different kinds of abstract memory may be used to give such machines finite descriptions.
874:
89:
220:, and a relatively stable measure of complexity in Turing machine programs by Shannon. In the same year,
6004:
5787:
5522:
5020:
4726:
326:
4414:
746:
6622:
6086:
5759:
5408:
4622:
4299:
4218:
4187:
2776:
2514:
2498:
802:
6482:
6415:
6410:
6373:
5904:
5877:
5847:
5777:
5704:
5679:
5542:
5190:
4796:
4547:
3337:
250:
3592:
3423:
2852:
Normally automata theory describes the states of abstract machines but there are discrete automata,
6339:
6334:
6243:
6203:
5919:
5628:
5461:
5047:
4916:
4699:
4694:
3929:, The Quarterly Journal of Mathematics, vol. 69, Oxford University Press, pp. 1089–1099,
3275:
3192:
3003:
2770:
2654:
2617:
2542:
274:
265:, along with the computational equivalence of deterministic and nondeterministic finite automata.
106:
3842:
2676:
Which class of formal languages is recognizable by some type of automata? (Recognizable languages)
2030:
1552:
1040:
6528:
5689:
5623:
5514:
5330:
4990:
3341:
2564:
2451:
1417:. Similarly, at each step, the automaton emits an output symbol according to the output function
839:
270:
246:
174:
134:
6164:
1951:
939:
285:
What follows is a general definition of an automaton, which restricts a broader definition of a
6533:
6523:
6497:
6319:
6314:
6309:
6304:
6262:
6225:
6171:
5897:
5887:
5865:
5754:
5585:
5466:
5233:
5223:
5218:
4710:
4648:
4573:
3321:
3291:
2811:
2428:
2649:: An automaton need not strictly accept or reject an input. It may accept the input with some
1929:
1791:
624:
330:. The symbols received by the automaton as input at any step are a sequence of symbols called
177:
was developed under different names by different research communities. The earlier concept of
6450:
6430:
6368:
6297:
6076:
6054:
6029:
5929:
5724:
5694:
5684:
5580:
5494:
5370:
5310:
5277:
5267:
5150:
5115:
5105:
5042:
4911:
4886:
4881:
4846:
4653:
4601:
3860:
3794:
2763:
2598:
2371:
1909:
1480:
557:
505:
475:
181:
was also included in the discipline along with new forms of infinite-state automata, such as
170:
130:
126:
85:
3927:
Irreducible compositions of degree two polynomials over finite fields have regular structure
6608:
6502:
6487:
6402:
6329:
6292:
6287:
6277:
6037:
5991:
5484:
5456:
5428:
5423:
5252:
5228:
5180:
5163:
5158:
5140:
5130:
5125:
5087:
5037:
5032:
4949:
4895:
4746:
4721:
4578:
4539:
4288:
3251:
3010:
2985:
2958:
2930:
2731:
2546:
1393:
1362:
1280:
1253:
1226:
1199:
1172:
1145:
102:
4317:
4260:
4236:
4205:
2801:
8:
6477:
6346:
6257:
6144:
6115:
5839:
5749:
5674:
5590:
5575:
5340:
5120:
5077:
5072:
4969:
4959:
4931:
2472:
213:
153:
The theory of abstract automata was developed in the mid-20th century in connection with
142:
3199:
3167:
3135:
3103:
3071:
3037:
2896:
2588:: This idea is quite similar to tree automata but orthogonal. The automaton may run its
1640:
342:
one of its states. When the automaton receives new input, it moves to another state (or
6614:
6267:
6253:
6235:
6218:
6198:
6181:
6091:
5914:
5714:
5613:
5489:
5446:
5355:
5297:
5282:
5272:
5057:
4856:
4731:
4673:
4617:
4368:
4244:
4180:
3986:
3948:
3930:
3878:
3823:
3698:
3467:. Therefore, in the most general case, categories of variable automata of any kind are
3271:
2837:
2757:
2683:
under union, intersection, or complementation of formal languages? (Closure properties)
2503:
2207:
2010:
1990:
1873:
1853:
1683:
1663:
1620:
740:
710:
690:
531:
166:
93:
3744:
3675:
3514:
2796:
2432:
instead of sequence of symbols. In this case after reading each symbol, the automaton
6440:
6176:
6154:
6081:
6042:
6019:
5808:
5734:
5664:
5643:
5605:
5413:
5380:
5360:
5052:
4964:
4838:
4466:
4384:
4349:
4303:
4278:
4252:
4222:
4191:
4161:
4136:
4112:
4102:
4029:
4021:
4004:
3905:
3584:
3580:
3540:
3392:
3263:
2822:
225:
217:
182:
122:
4048:
3702:
1549:
to describe the machine's behavior when fed whole input words. For the empty string
6358:
6149:
6137:
6120:
6098:
6047:
5999:
5860:
5567:
5451:
5418:
5213:
5135:
5024:
5010:
5005:
4954:
4941:
4866:
4819:
4715:
4668:
4635:
4481:
4313:
4256:
4232:
4201:
4094:
3990:
3978:
3952:
3940:
3782:
3759:
3739:
3690:
3576:
3479:, and also a subcategory of the 2-category of groupoids, or the groupoid category.
3259:
2861:
2830:
2826:
2737:
2705:
2691:
2379:
1899:
728:
389:
an input sequence. The set of all the words accepted by an automaton is called the
258:
201:
162:
110:
77:
6464:
6420:
6247:
6191:
6186:
6125:
5947:
5638:
5532:
5504:
5398:
5350:
5335:
5320:
5170:
5110:
5000:
4974:
4926:
4871:
4678:
4593:
4560:
4476:
4449:
4341:
4285:
4275:
3899:
3819:
3267:
3247:
3243:
3239:
2853:
2818:
2704:
For a given formal language, what is the smallest automaton that recognizes it? (
2669:
Different combinations of the above variations produce many classes of automata.
2662:
2416:
1781:{\displaystyle {\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)}
370:
315:
229:
209:
154:
117:
2268:
by an automaton is the set of all the words that are accepted by the automaton,
6108:
5744:
5648:
5547:
5393:
5365:
4689:
4471:
4453:
4126:
4098:
4093:
3408:
3283:
2783:
2613:
2538:
2441:
2411:
369:
To investigate the possible state/input/output sequences in an automaton using
193:
178:
158:
3238:
Each model in automata theory plays important roles in several applied areas.
2501:
in which symbols can be pushed and popped. This kind of automaton is called a
2355:{\displaystyle L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}}
6637:
6425:
6380:
6363:
6009:
5882:
5633:
4921:
4774:
4363:
4267:
3694:
2529:: The inputs and outputs of automata are often described as input and output
2519:
205:
197:
54:
3982:
2382:. For different types of automata, the recognizable languages are different.
113:, which takes the previous state and current input symbol as its arguments.
6445:
6324:
6103:
6014:
5909:
5729:
5388:
4175:
3944:
3671:
3287:
2436:
all the successor symbols in the input tree. It is said that the automaton
221:
3588:
2578:
decides to jump into one of the allowed choices. Such automata are called
6556:
6472:
5719:
5345:
5257:
4741:
4663:
4588:
4444:
4409:
4151:
3904:. Singapore: World Scientific Publishing Co. Pte. Ltd. pp. 155–156.
3723:
3279:
2650:
238:, an accessible textbook explaining automata and information using basic
3515:"The Structures of Computation and the Mathematical Structure of Nature"
3258:
and artificial intelligence. Originally, CFGs were used in the study of
6492:
5739:
5669:
5262:
4995:
4851:
3786:
3763:
3476:
262:
239:
2698:
Does an automaton accept at least one input word? (Emptiness checking)
2487:: An automaton that may not have a finite number of states, or even a
6540:
The
Unreasonable Effectiveness of Mathematics in the Natural Sciences
5855:
5244:
5205:
3877:
Moore, Cristopher (2019-07-31). "Automata, languages, and grammars".
3493:
3371:
2864:, which use digital data, analog data or continuous time, or digital
2488:
81:
3617:
Ashby, W. R.; et al. (1956). C.E. Shannon; J. McCarthy (eds.).
2374:
are the set of languages that are recognized by some automaton. For
463:{\displaystyle M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle }
157:. Automata theory was initially considered a branch of mathematical
5305:
4788:
3935:
3883:
3463:
2497:: An automaton may also contain some extra memory in the form of a
4324:
4186:. Encyclopedia of Mathematics and Its Applications. Vol. 25.
2690:
Automata theory also studies the existence or nonexistence of any
2392:
variations in the definition of different components of automata.
1850:, which gives the complete output of the machine when run on word
3345:
2616:. Automata which can move back-and-forth on the input are called
2602:. The acceptance condition must be satisfied on all runs of such
412:
338:. At each moment during a run of the automaton, the automaton is
257:, also useful in regularity proofs, was proven in this period by
138:
4404:
6595:
European
Community on Computational Methods in Applied Sciences
6159:
5977:
4157:
Automata, Computability and
Complexity: Theory and Applications
3388:
1169:. In other words, at first the automaton is at the start state
397:, which accepts or rejects attempts to enter the correct code.
393:. A familiar example of a machine recognizing a language is an
286:
1542:{\displaystyle {\overline {\delta }}:Q\times \Sigma ^{*}\to Q}
4704:
4340:
3658:
An
Introduction to Kolmogorov Complexity and its Applications
49:
6590:
International
Council for Industrial and Applied Mathematics
4773:
Each category of languages, except those marked by a , is a
3348:. An automata homomorphism maps a quintuple of an automaton
2847:
2481:: An automaton that contains only a finite number of states.
4108:
Introduction to
Automata Theory, Languages, and Computation
3901:
3475:. Moreover, the category of reversible automata is then a
4073:
Meseguer, J., Montanari, U.: 1990 Petri nets are monoids.
3391:
are also considered as a suitable setting for automata in
2717:
The following is an incomplete list of types of automata.
313:). An automaton processes one input picked from a set of
3924:
1277:
in the input string, the automaton picks the next state
42:(Clicking on each layer gets an article on that subject)
4381:
Introduction to
Languages and The Theory of Computation
4334:
Producing a top-down parse order with bottom-up parsing
1610:{\displaystyle {\overline {\delta }}(q,\varepsilon )=q}
5838:
3964:
6209:
Numerical methods for ordinary differential equations
3965:
Chakraborty, P.; Saxena, P. C.; Katti, C. P. (2011).
3426:
3202:
3170:
3138:
3106:
3074:
3040:
3013:
2988:
2961:
2933:
2899:
2633:: Same as described in the informal definition above.
2274:
2238:
2210:
2155:
2076:
2033:
2013:
1993:
1954:
1932:
1912:
1876:
1856:
1814:
1794:
1706:
1686:
1666:
1643:
1623:
1575:
1555:
1503:
1483:
1423:
1396:
1365:
1310:
1283:
1256:
1229:
1202:
1175:
1148:
1079:
1043:
975:
942:
877:
842:
805:
749:
713:
693:
650:
627:
587:
560:
534:
508:
478:
420:
362:. A state at which the automaton halts is called the
6585:
Société de Mathématiques Appliquées et Industrielles
6578:
Japan Society for Industrial and Applied Mathematics
6214:
Numerical methods for partial differential equations
5928:
6401:
3814:
3812:
3810:
3366:. Automata homomorphisms can also be considered as
2732:
Nondeterministic/Deterministic finite-state machine
2197:{\displaystyle {\overline {\delta }}(q_{0},w)\in F}
2138:{\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}
675:{\displaystyle \lambda :Q\times \Sigma \to \Gamma }
4367:
4179:
3452:
3215:
3183:
3151:
3119:
3087:
3053:
3019:
2994:
2967:
2939:
2912:
2386:
2354:
2257:
2216:
2196:
2137:
2045:
2019:
1999:
1973:
1938:
1918:
1898:In order to study an automaton with the theory of
1882:
1862:
1842:
1800:
1780:
1692:
1672:
1652:
1629:
1609:
1561:
1541:
1489:
1464:
1409:
1378:
1351:
1296:
1269:
1242:
1215:
1188:
1161:
1134:
1061:
1029:
961:
928:
855:
824:
791:
719:
699:
674:
633:
611:
566:
540:
514:
484:
462:
4049:http://www.math.cornell.edu/~worthing/asl2010.pdf
4011:. Kluwer Academic Publishers:Dordrecht and Prague
3925:Ferraguti, A.; Micheli, G.; Schnyder, R. (2018),
3843:"Computational complexity of recursive sequences"
3828:Algebraic Structure Theory of Sequential Machines
3539:. New York: John Wiley & Sons. p. 1-13.
2694:to solve problems similar to the following list:
1135:{\displaystyle a_{1}a_{2}...a_{n}\in \Sigma ^{*}}
88:that can be solved using them. It is a theory in
6635:
3840:
3818:
3807:
3732:Proceedings of the American Mathematical Society
2513:: An automaton may have memory in the form of a
2471:, performs a transformation which may implement
173:to describe material systems. The theory of the
4298:. Translated from the French by Reuben Thomas.
4251:. Chapman and Hall Mathematics Series. London:
4062:"Monoidal Functors, Species, and Hopf Algebras"
2871:
2204:, that is, if after consuming the whole string
192:, which collected work by scientists including
27:
6573:Society for Industrial and Applied Mathematics
4378:
4125:
3967:"Fifty Years of Automata Simulation: A Review"
3676:"Three models for the description of language"
3621:. Princeton, N.J.: Princeton University Press.
619:mapping state-input pairs to successor states,
411:An automaton can be represented formally by a
5824:
4828:Note: This template roughly follows the 2012
4804:
4430:
4362:
4217:. With contributions by Tom Head. Cambridge:
3861:"A Short History of Computational Complexity"
3768:"Finite Automata and Their Decision Problems"
3562:"The Place of the Brain in the Natural World"
3380:, of the automaton is defined as a semigroup
2467:: An automaton with one state, also called a
1906:, replacing the output alphabet and function
522:is another finite set of symbols, called the
65:as an accepting state. Since all paths from S
6391:Supersymmetric theory of stochastic dynamics
3858:
3636:
3634:
3632:
3630:
3628:
3315:
2410:: An automaton that accepts infinite words (
2349:
2281:
1700:is the (possibly empty) rest of the string,
1030:{\displaystyle q_{i}=\delta (q_{i-1},a_{i})}
612:{\displaystyle \delta :Q\times \Sigma \to Q}
457:
427:
4752:Counter-free (with aperiodic finite monoid)
4293:
4150:
3789:. Archived from the original on 2010-12-14.
2596:next read symbol. Such automata are called
1843:{\displaystyle {\overline {\lambda }}(q,w)}
5831:
5817:
4811:
4797:
4437:
4423:
3758:
3336:defining the arrows between automata is a
1386:has been read, leaving the machine in the
4370:Computation: Finite and infinite machines
4132:Introduction to the Theory of Computation
3934:
3882:
3743:
3625:
3357:onto the quintuple of another automaton
2848:Discrete, continuous, and hybrid automata
4346:Automata Theory: An Engineering Approach
4215:Automata theory with modern applications
4212:
4026:Categories for the Working Mathematician
4020:
3891:
3830:. Englewood Cliffs, N.J.: Prentice-Hall.
3660:. New York: Springer-Verlag. p. 84.
3645:. Englewood Cliffs, N.J.: Prentice-Hall.
3286:. Automata also appear in the theory of
2062:This allows the following to be defined:
228:, a correspondence between automata and
48:
4174:
3775:IBM Journal of Research and Development
3670:
3537:Sequential Machines and Automata Theory
1902:, an automaton may be considered as an
1465:{\displaystyle \lambda (q_{i-1},a_{i})}
292:
16:Study of abstract machines and automata
6636:
5528:Knowledge representation and reasoning
4644:Linear context-free rewriting language
4243:
3841:Hartmanis, J.; Stearns, R. E. (1964).
3722:
3683:IRE Transactions on Information Theory
3655:
3301:
2258:{\displaystyle L\subseteq \Sigma ^{*}}
1352:{\displaystyle \delta (q_{i-1},a_{i})}
116:Automata theory is closely related to
5812:
5553:Philosophy of artificial intelligence
4792:
4569:Linear context-free rewriting systems
4418:
3876:
3859:Fortnow, Lance; Homer, Steve (2002).
3640:
3616:
3559:
3534:
3374:homomorphisms, when the state space,
1304:according to the transition function
929:{\displaystyle q_{0},q_{1},...,q_{n}}
836:. The set of all words is denoted by
682:mapping state-input pairs to outputs.
4872:Energy consumption (Green computing)
4818:
3282:, and was popularized in America by
3063:Nondeterministic Push Down Automaton
2977:Nondeterministic Push Down Automaton
2751:deterministic context-free languages
2712:
400:
391:language recognized by the automaton
373:theory, a machine can be assigned a
5558:Distributed artificial intelligence
4830:ACM Computing Classification System
4249:Regular algebra and finite machines
4111:(2nd ed.). Pearson Education.
4009:Automata and Algebras in Categories
3897:
3512:
2862:hybrid discrete-continuous automata
2653:between zero and one. For example,
255:pumping lemma for regular languages
13:
5840:Industrial and applied mathematics
5063:Integrated development environment
4777:of the category directly above it.
4087:
3728:"Linear Automaton Transformations"
3560:Ashby, William Ross (1967-01-15).
2291:
2246:
2224:the machine is in an accept state.
2126:
1913:
1524:
1123:
844:
819:
792:{\displaystyle a_{1}a_{2}...a_{n}}
669:
663:
600:
509:
479:
436:
430:
301:when it is given some sequence of
23:
14:
6655:
6070:Stochastic differential equations
5538:Automated planning and scheduling
5068:Software configuration management
4398:
4374:. Princeton, N.J.: Prentice Hall.
3745:10.1090/S0002-9939-1958-0135681-9
3029:Deterministic Push Down Automaton
2950:Deterministic Push Down Automaton
2947: (below is stronger)
2923:Nondeterministic Finite Automaton
2808:Nondeterministic Büchi automaton
6386:Supersymmetric quantum mechanics
5792:
5782:
5773:
5772:
4060:Aguiar, M. and Mahajan, S.2010.
3712:from the original on 2016-03-07.
3656:Li, Ming; Paul, Vitanyi (1997).
3320:One can define several distinct
3270:, the most famous example being
2789:recursively enumerable languages
2745:Deterministic pushdown automaton
2533:. Some machines have additional
825:{\displaystyle a_{i}\in \Sigma }
53:The automaton described by this
6268:Stochastic variational calculus
6060:Ordinary differential equations
5783:
5186:Computational complexity theory
4067:
4054:
4042:
4014:
3997:
3958:
3918:
3870:
3852:
3834:
3399:Categories of variable automata
3233:
3225:Multidimensional Turing Machine
3129:Nondeterministic Turing Machine
2927:(above is weaker)
2387:Variant definitions of automata
2378:the recognizable languages are
1808:may be extended similarly into
6065:Partial differential equations
5938:Arbitrary-precision arithmetic
4970:Network performance evaluation
3752:
3716:
3664:
3649:
3610:
3553:
3528:
3506:
3453:{\displaystyle A_{i}\to A_{i}}
3437:
3296:induction of regular languages
3209:
3204:
3177:
3172:
3145:
3140:
3113:
3108:
3081:
3076:
3047:
3042:
2906:
2901:
2888:Deterministic Finite Automaton
2665:have probabilistic acceptance.
2340:
2321:
2304:
2185:
2166:
1837:
1825:
1775:
1766:
1754:
1741:
1732:
1717:
1598:
1586:
1533:
1459:
1427:
1346:
1314:
1024:
992:
666:
603:
235:An Introduction to Cybernetics
1:
5953:Interactive geometry software
5341:Multimedia information system
5326:Geographic information system
5316:Enterprise information system
4905:Computer systems organization
4294:Sakarovitch, Jacques (2009).
3643:Theories of Abstract Automata
3499:
3489:Boolean differential calculus
3414:The Human Use of Human Beings
1497:is extended inductively into
1073:of the automaton on an input
5700:Computational social science
5288:Theoretical computer science
5101:Software development process
4877:Electronic design automation
4862:Very Large Scale Integration
3581:10.1016/0303-2647(67)90021-4
3161:Probabilistic Turing Machine
3097:Deterministic Turing Machine
2872:Hierarchy in terms of powers
2637:Acceptance of infinite words
2414:). Such automata are called
2316:
2161:
2046:{\displaystyle F\subseteq Q}
1820:
1749:
1712:
1581:
1562:{\displaystyle \varepsilon }
1509:
1062:{\displaystyle 0<i\leq n}
739:An automaton reads a finite
334:. An automaton has a set of
188:1956 saw the publication of
90:theoretical computer science
7:
6005:Computational number theory
5968:Numerical-analysis software
5523:Natural language processing
5311:Information storage systems
4296:Elements of automata theory
4213:Anderson, James A. (2006).
4075:Information and Computation
3482:
3332:, and Turing machines with
2868:analog data, respectively.
2777:context-sensitive languages
2517:. Such a machine is called
856:{\displaystyle \Sigma ^{*}}
280:
232:, and Ross Ashby published
10:
6660:
5439:Human–computer interaction
5409:Intrusion detection system
5321:Social information systems
5306:Database management system
4659:Deterministic context-free
4584:Deterministic context-free
4348:. New York: Crane Russak.
4300:Cambridge University Press
4219:Cambridge University Press
4188:Cambridge University Press
3569:Currents in Modern Biology
3340:, it has both categorical
2893:(same power)
2631:Acceptance of finite words
1974:{\displaystyle q_{0}\in Q}
962:{\displaystyle q_{i}\in Q}
354:produces symbols from the
148:
92:with close connections to
6603:
6565:
6549:
6511:
6463:
6411:Algebra of physical space
6276:
6234:
6028:
5990:
5878:Automated theorem proving
5846:
5768:
5705:Computational engineering
5680:Computational mathematics
5657:
5604:
5566:
5513:
5475:
5437:
5379:
5296:
5242:
5204:
5149:
5086:
5019:
4983:
4940:
4904:
4837:
4826:
4770:
4732:Nondeterministic pushdown
4460:
4383:. New York: McGraw Hill.
4344:; F. Keith Hanna (1975).
4336:. Elsevier North-Holland.
3799:: CS1 maint: unfit URL (
3338:Cartesian closed category
3316:Category-theoretic models
3266:are used in the field of
2920: (same power)
2810:
2580:nondeterministic automata
305:in discrete (individual)
6204:Numerical linear algebra
5715:Computational healthcare
5710:Differentiable computing
5629:Graphics processing unit
5048:Domain-specific language
4917:Computational complexity
4182:Computation and automata
3695:10.1109/TIT.1956.1056813
3517:. The Rutherford Journal
3403:One could also define a
3368:automata transformations
3193:Multitape Turing Machine
3067:with 2 push-down stores
3033:with 2 push-down stores
3004:Linear Bounded Automaton
2771:Linear bounded automaton
2647:Probabilistic acceptance
2543:linear bounded automaton
1939:{\displaystyle \lambda }
1801:{\displaystyle \lambda }
1477:The transition function
1359:, until the last symbol
634:{\displaystyle \lambda }
275:computational complexity
5943:Finite element analysis
5893:Constraint satisfaction
5690:Computational chemistry
5624:Photograph manipulation
5515:Artificial intelligence
5331:Decision support system
4379:John C. Martin (2011).
3983:10.1145/2038876.2038893
3641:Arbib, Michael (1969).
3469:categories of groupoids
3292:irreducible polynomials
2981:with 1 push-down store
2954:with 1 push-down store
2890:(DFA) -- Lowest Power
2726:Recognizable languages
2655:quantum finite automata
2618:two-way finite automata
2565:deterministic automaton
2523:and is Turing-complete.
2452:infinite tree automaton
1919:{\displaystyle \Gamma }
1680:is the last symbol and
1490:{\displaystyle \delta }
567:{\displaystyle \delta }
515:{\displaystyle \Gamma }
485:{\displaystyle \Sigma }
247:linear bounded automata
175:finite-state transducer
135:artificial intelligence
6644:Automata (computation)
6498:Mathematical economics
6172:Multivariable calculus
6055:Differential equations
5898:Constraint programming
5888:Computational geometry
5755:Educational technology
5586:Reinforcement learning
5336:Process control system
5234:Computational geometry
5224:Algorithmic efficiency
5219:Analysis of algorithms
4867:Systems on Chip (SoCs)
4737:Deterministic pushdown
4613:Recursively enumerable
4272:Automata and Languages
4028:. New York: Springer.
3535:Booth, Taylor (1967).
3454:
3334:automata homomorphisms
3217:
3185:
3153:
3121:
3089:
3055:
3021:
2996:
2969:
2941:
2914:
2764:context-free languages
2372:recognizable languages
2367:Recognizable languages
2356:
2259:
2218:
2198:
2139:
2047:
2021:
2001:
1975:
1940:
1920:
1884:
1864:
1844:
1802:
1788:. The output function
1782:
1694:
1674:
1654:
1631:
1611:
1563:
1543:
1491:
1466:
1411:
1380:
1353:
1298:
1271:
1244:
1217:
1190:
1163:
1136:
1063:
1031:
963:
930:
857:
826:
793:
721:
701:
676:
635:
613:
568:
542:
516:
486:
464:
86:computational problems
70:
35:
6451:Supersymmetry algebra
6436:Representation theory
6431:Renormalization group
6077:Differential geometry
5958:Optimization software
5930:Mathematical software
5725:Electronic publishing
5695:Computational biology
5685:Computational physics
5581:Unsupervised learning
5495:Distributed computing
5371:Information retrieval
5278:Mathematical analysis
5268:Mathematical software
5151:Theory of computation
5116:Software construction
5106:Requirements analysis
4984:Software organization
4912:Computer architecture
4882:Hardware acceleration
4847:Printed circuit board
3898:Yan, Song Y. (1998).
3455:
3256:programming languages
3218:
3186:
3154:
3122:
3090:
3056:
3022:
3020:{\displaystyle \cap }
2997:
2995:{\displaystyle \cap }
2970:
2968:{\displaystyle \cap }
2942:
2940:{\displaystyle \cap }
2915:
2679:Are certain automata
2576:non-deterministically
2469:combinational circuit
2426:: The input may be a
2357:
2260:
2219:
2199:
2149:for the automaton if
2140:
2048:
2022:
2007:, a set of states of
2002:
1976:
1941:
1921:
1885:
1865:
1845:
1803:
1783:
1695:
1675:
1655:
1632:
1612:
1564:
1544:
1492:
1467:
1412:
1410:{\displaystyle q_{n}}
1381:
1379:{\displaystyle a_{n}}
1354:
1299:
1297:{\displaystyle q_{i}}
1272:
1270:{\displaystyle a_{i}}
1245:
1243:{\displaystyle a_{1}}
1218:
1216:{\displaystyle a_{1}}
1196:, and receives input
1191:
1189:{\displaystyle q_{0}}
1164:
1162:{\displaystyle q_{0}}
1137:
1064:
1032:
964:
931:
871:A sequence of states
858:
832:, which is called an
827:
794:
722:
702:
677:
636:
614:
569:
543:
517:
487:
465:
323:, which is called an
251:Myhill–Nerode theorem
171:differential calculus
131:compiler construction
127:theory of computation
52:
34:
6503:Mathematical finance
6488:Social choice theory
6403:Algebraic structures
6352:in quantum mechanics
6288:Analytical mechanics
6254:Stochastic processes
6226:Variational calculus
6038:Approximation theory
5963:Statistical software
5485:Concurrent computing
5457:Ubiquitous computing
5429:Application security
5424:Information security
5253:Discrete mathematics
5229:Randomized algorithm
5181:Computability theory
5159:Model of computation
5131:Software maintenance
5126:Software engineering
5088:Software development
5038:Programming language
5033:Programming paradigm
4950:Network architecture
4722:Tree stack automaton
3945:10.1093/qmath/hay015
3513:Mahoney, Michael S.
3424:
3307:can be defined in a
3252:Context-free grammar
3200:
3168:
3136:
3104:
3072:
3038:
3011:
2986:
2959:
2931:
2897:
2692:effective algorithms
2625:Acceptance condition
2606:to accept the input.
2599:alternating automata
2547:log-space transducer
2272:
2236:
2208:
2153:
2074:
2031:
2011:
1991:
1952:
1930:
1910:
1874:
1854:
1812:
1792:
1704:
1684:
1664:
1641:
1621:
1573:
1553:
1501:
1481:
1421:
1394:
1363:
1308:
1281:
1254:
1250:and every following
1227:
1200:
1173:
1146:
1142:starting from state
1077:
1041:
973:
940:
875:
840:
803:
747:
711:
691:
648:
643:next-output function
625:
585:
558:
532:
506:
476:
418:
293:Informal description
103:finite-state machine
39:Classes of automata
6478:Operations research
6347:Perturbation theory
6145:Multilinear algebra
6116:Functional analysis
5973:Numerical libraries
5905:Computational logic
5760:Document management
5750:Operations research
5675:Enterprise software
5591:Multi-task learning
5576:Supervised learning
5298:Information systems
5121:Software deployment
5078:Software repository
4932:Real-time computing
4630:range concatenation
4555:range concatenation
3473:groupoid categories
3462:variable automaton
3393:monoidal categories
3330:sequential automata
3326:sequential machines
3302:Automata simulators
3254:(CFGs) are used in
2858:continuous automata
2812:ω-regular languages
2554:Transition function
2473:combinational logic
2448:Infinite tree input
2229:Recognized language
580:transition function
576:next-state function
492:is a finite set of
348:transition function
214:Stephen Cole Kleene
167:information systems
143:formal verification
111:transition function
6615:Mathematics portal
6512:Other applications
6236:Probability theory
6219:Validated numerics
6199:Numerical analysis
6092:Geometric analysis
6082:Differential forms
5915:Information theory
5543:Search methodology
5490:Parallel computing
5447:Interaction design
5356:Computing platform
5283:Numerical analysis
5273:Information theory
5058:Software framework
5021:Software notations
4960:Network components
4857:Integrated circuit
4405:dk.brics.automaton
4326:James P. Schmeiser
4253:Chapman & Hall
4135:. PWS Publishing.
4022:Mac Lane, Saunders
3787:10.1147/rd.32.0114
3450:
3420:the endomorphisms
3407:, in the sense of
3405:variable automaton
3216:{\displaystyle ||}
3213:
3184:{\displaystyle ||}
3181:
3152:{\displaystyle ||}
3149:
3120:{\displaystyle ||}
3117:
3088:{\displaystyle ||}
3085:
3054:{\displaystyle ||}
3051:
3017:
2992:
2965:
2937:
2913:{\displaystyle ||}
2910:
2838:Weighted automaton
2758:Pushdown automaton
2659:geometric automata
2504:pushdown automaton
2352:
2255:
2214:
2194:
2135:
2043:
2017:
1997:
1971:
1936:
1916:
1880:
1860:
1840:
1798:
1778:
1690:
1670:
1653:{\displaystyle wa}
1650:
1637:, and for strings
1627:
1607:
1559:
1539:
1487:
1462:
1407:
1376:
1349:
1294:
1267:
1240:
1213:
1186:
1159:
1132:
1059:
1027:
959:
926:
853:
822:
789:
717:
697:
672:
631:
609:
564:
538:
512:
482:
460:
271:universal gate set
101:automaton (FA) or
94:mathematical logic
71:
36:
6631:
6630:
6465:Decision sciences
6459:
6458:
6441:Spacetime algebra
6133:Harmonic analysis
6099:Dynamical systems
6043:Clifford analysis
6020:Discrete geometry
5986:
5985:
5806:
5805:
5735:Electronic voting
5665:Quantum Computing
5658:Applied computing
5644:Image compression
5414:Hardware security
5404:Security services
5361:Digital marketing
5141:Open-source model
5053:Modeling language
4965:Network scheduler
4786:
4785:
4765:
4764:
4727:Embedded pushdown
4623:Context-sensitive
4548:Context-sensitive
4482:Abstract machines
4467:Chomsky hierarchy
4390:978-0-07-319146-1
4355:978-0-8448-0657-0
4309:978-0-521-84425-3
4228:978-0-521-61324-8
4197:978-0-521-30245-6
4167:978-0-13-228806-4
4142:978-0-534-94728-6
4118:978-0-201-44124-6
4103:Jeffrey D. Ullman
4035:978-0-387-90036-0
3911:978-981-02-3422-5
3309:symbolic language
3264:Cellular automata
3246:, compilers, and
3231:
3230:
2845:
2844:
2823:Streett automaton
2802:ω-limit languages
2738:regular languages
2713:Types of automata
2380:regular languages
2319:
2310:
2302:
2217:{\displaystyle w}
2164:
2020:{\displaystyle Q}
2000:{\displaystyle F}
1883:{\displaystyle q}
1863:{\displaystyle w}
1823:
1752:
1715:
1693:{\displaystyle w}
1673:{\displaystyle a}
1630:{\displaystyle q}
1584:
1512:
720:{\displaystyle M}
700:{\displaystyle Q}
541:{\displaystyle Q}
526:of the automaton,
500:of the automaton,
401:Formal definition
226:Chomsky hierarchy
218:regular languages
183:pushdown automata
123:Chomsky hierarchy
84:, as well as the
78:abstract machines
57:starts in state S
6651:
6416:Feynman integral
6399:
6398:
6359:Potential theory
6248:random variables
6138:Fourier analysis
6121:Operator algebra
6048:Clifford algebra
6000:Computer algebra
5926:
5925:
5833:
5826:
5819:
5810:
5809:
5796:
5795:
5786:
5785:
5776:
5775:
5596:Cross-validation
5568:Machine learning
5452:Social computing
5419:Network security
5214:Algorithm design
5136:Programming team
5096:Control variable
5073:Software library
5011:Software quality
5006:Operating system
4955:Network protocol
4820:Computer science
4813:
4806:
4799:
4790:
4789:
4781:
4778:
4742:Visibly pushdown
4716:Thread automaton
4664:Visibly pushdown
4632:
4589:Visibly pushdown
4557:
4544:(no common name)
4463:
4462:
4450:formal languages
4439:
4432:
4425:
4416:
4415:
4394:
4375:
4373:
4359:
4337:
4330:David T. Barnard
4321:
4264:
4240:
4209:
4185:
4171:
4146:
4122:
4095:John E. Hopcroft
4081:
4071:
4065:
4058:
4052:
4046:
4040:
4039:
4018:
4012:
4003:Jirí Adámek and
4001:
3995:
3994:
3962:
3956:
3955:
3938:
3922:
3916:
3915:
3895:
3889:
3888:
3886:
3874:
3868:
3867:
3865:
3856:
3850:
3849:
3847:
3838:
3832:
3831:
3816:
3805:
3804:
3798:
3790:
3772:
3756:
3750:
3749:
3747:
3720:
3714:
3713:
3711:
3680:
3668:
3662:
3661:
3653:
3647:
3646:
3638:
3623:
3622:
3619:Automata Studies
3614:
3608:
3606:
3604:
3603:
3597:
3591:. Archived from
3566:
3557:
3551:
3550:
3532:
3526:
3525:
3523:
3522:
3510:
3459:
3457:
3456:
3451:
3449:
3448:
3436:
3435:
3222:
3220:
3219:
3214:
3212:
3207:
3190:
3188:
3187:
3182:
3180:
3175:
3158:
3156:
3155:
3150:
3148:
3143:
3126:
3124:
3123:
3118:
3116:
3111:
3094:
3092:
3091:
3086:
3084:
3079:
3060:
3058:
3057:
3052:
3050:
3045:
3026:
3024:
3023:
3018:
3001:
2999:
2998:
2993:
2974:
2972:
2971:
2966:
2946:
2944:
2943:
2938:
2919:
2917:
2916:
2911:
2909:
2904:
2879:
2878:
2831:Muller automaton
2827:Parity automaton
2720:
2719:
2572:Nondeterministic
2537:, including the
2361:
2359:
2358:
2353:
2333:
2332:
2320:
2312:
2308:
2307:
2300:
2299:
2298:
2264:
2262:
2261:
2256:
2254:
2253:
2223:
2221:
2220:
2215:
2203:
2201:
2200:
2195:
2178:
2177:
2165:
2157:
2144:
2142:
2141:
2136:
2134:
2133:
2121:
2120:
2102:
2101:
2092:
2091:
2052:
2050:
2049:
2044:
2026:
2024:
2023:
2018:
2006:
2004:
2003:
1998:
1980:
1978:
1977:
1972:
1964:
1963:
1945:
1943:
1942:
1937:
1925:
1923:
1922:
1917:
1900:formal languages
1889:
1887:
1886:
1881:
1869:
1867:
1866:
1861:
1849:
1847:
1846:
1841:
1824:
1816:
1807:
1805:
1804:
1799:
1787:
1785:
1784:
1779:
1753:
1745:
1716:
1708:
1699:
1697:
1696:
1691:
1679:
1677:
1676:
1671:
1659:
1657:
1656:
1651:
1636:
1634:
1633:
1628:
1616:
1614:
1613:
1608:
1585:
1577:
1568:
1566:
1565:
1560:
1548:
1546:
1545:
1540:
1532:
1531:
1513:
1505:
1496:
1494:
1493:
1488:
1471:
1469:
1468:
1463:
1458:
1457:
1445:
1444:
1416:
1414:
1413:
1408:
1406:
1405:
1385:
1383:
1382:
1377:
1375:
1374:
1358:
1356:
1355:
1350:
1345:
1344:
1332:
1331:
1303:
1301:
1300:
1295:
1293:
1292:
1276:
1274:
1273:
1268:
1266:
1265:
1249:
1247:
1246:
1241:
1239:
1238:
1222:
1220:
1219:
1214:
1212:
1211:
1195:
1193:
1192:
1187:
1185:
1184:
1168:
1166:
1165:
1160:
1158:
1157:
1141:
1139:
1138:
1133:
1131:
1130:
1118:
1117:
1099:
1098:
1089:
1088:
1068:
1066:
1065:
1060:
1036:
1034:
1033:
1028:
1023:
1022:
1010:
1009:
985:
984:
968:
966:
965:
960:
952:
951:
935:
933:
932:
927:
925:
924:
900:
899:
887:
886:
862:
860:
859:
854:
852:
851:
831:
829:
828:
823:
815:
814:
798:
796:
795:
790:
788:
787:
769:
768:
759:
758:
729:finite automaton
726:
724:
723:
718:
707:is finite, then
706:
704:
703:
698:
681:
679:
678:
673:
640:
638:
637:
632:
618:
616:
615:
610:
573:
571:
570:
565:
547:
545:
544:
539:
521:
519:
518:
513:
491:
489:
488:
483:
469:
467:
466:
461:
379:accepting states
259:Michael O. Rabin
202:John von Neumann
190:Automata Studies
163:abstract algebra
76:is the study of
43:
26:
6659:
6658:
6654:
6653:
6652:
6650:
6649:
6648:
6634:
6633:
6632:
6627:
6599:
6561:
6545:
6507:
6455:
6421:Poisson algebra
6397:
6279:
6272:
6230:
6126:Operator theory
6024:
5982:
5948:Tensor software
5924:
5873:Automata theory
5842:
5837:
5807:
5802:
5793:
5764:
5745:Word processing
5653:
5639:Virtual reality
5600:
5562:
5533:Computer vision
5509:
5505:Multiprocessing
5471:
5433:
5399:Security hacker
5375:
5351:Digital library
5292:
5243:Mathematics of
5238:
5200:
5176:Automata theory
5171:Formal language
5145:
5111:Software design
5082:
5015:
5001:Virtual machine
4979:
4975:Network service
4936:
4927:Embedded system
4900:
4833:
4822:
4817:
4787:
4782:
4779:
4772:
4766:
4761:
4683:
4627:
4606:
4552:
4533:
4456:
4454:formal grammars
4446:Automata theory
4443:
4401:
4391:
4356:
4342:Igor Aleksander
4310:
4276:Clarendon Press
4229:
4198:
4168:
4143:
4119:
4090:
4088:Further reading
4085:
4084:
4072:
4068:
4059:
4055:
4047:
4043:
4036:
4019:
4015:
4002:
3998:
3963:
3959:
3923:
3919:
3912:
3896:
3892:
3875:
3871:
3863:
3857:
3853:
3845:
3839:
3835:
3817:
3808:
3792:
3791:
3770:
3757:
3753:
3721:
3717:
3709:
3678:
3669:
3665:
3654:
3650:
3639:
3626:
3615:
3611:
3601:
3599:
3595:
3564:
3558:
3554:
3547:
3533:
3529:
3520:
3518:
3511:
3507:
3502:
3485:
3444:
3440:
3431:
3427:
3425:
3422:
3421:
3411:in his book on
3386:
3365:
3356:
3318:
3304:
3268:artificial life
3260:human languages
3248:hardware design
3244:text processing
3240:Finite automata
3236:
3223:
3208:
3203:
3201:
3198:
3197:
3196:
3191:
3176:
3171:
3169:
3166:
3165:
3164:
3159:
3144:
3139:
3137:
3134:
3133:
3132:
3127:
3112:
3107:
3105:
3102:
3101:
3100:
3095:
3080:
3075:
3073:
3070:
3069:
3068:
3066:
3061:
3046:
3041:
3039:
3036:
3035:
3034:
3032:
3027:
3012:
3009:
3008:
3007:
3002:
2987:
2984:
2983:
2982:
2980:
2975:
2960:
2957:
2956:
2955:
2953:
2948:
2932:
2929:
2928:
2926:
2921:
2905:
2900:
2898:
2895:
2894:
2891:
2874:
2854:analog automata
2850:
2819:Rabin automaton
2797:Büchi automaton
2715:
2663:metric automata
2590:multiple copies
2485:Infinite states
2429:tree of symbols
2389:
2376:finite automata
2328:
2324:
2311:
2303:
2294:
2290:
2273:
2270:
2269:
2249:
2245:
2237:
2234:
2233:
2209:
2206:
2205:
2173:
2169:
2156:
2154:
2151:
2150:
2129:
2125:
2116:
2112:
2097:
2093:
2087:
2083:
2075:
2072:
2071:
2032:
2029:
2028:
2012:
2009:
2008:
1992:
1989:
1988:
1981:, a designated
1959:
1955:
1953:
1950:
1949:
1931:
1928:
1927:
1911:
1908:
1907:
1875:
1872:
1871:
1855:
1852:
1851:
1815:
1813:
1810:
1809:
1793:
1790:
1789:
1744:
1707:
1705:
1702:
1701:
1685:
1682:
1681:
1665:
1662:
1661:
1642:
1639:
1638:
1622:
1619:
1618:
1617:for all states
1576:
1574:
1571:
1570:
1554:
1551:
1550:
1527:
1523:
1504:
1502:
1499:
1498:
1482:
1479:
1478:
1453:
1449:
1434:
1430:
1422:
1419:
1418:
1401:
1397:
1395:
1392:
1391:
1370:
1366:
1364:
1361:
1360:
1340:
1336:
1321:
1317:
1309:
1306:
1305:
1288:
1284:
1282:
1279:
1278:
1261:
1257:
1255:
1252:
1251:
1234:
1230:
1228:
1225:
1224:
1207:
1203:
1201:
1198:
1197:
1180:
1176:
1174:
1171:
1170:
1153:
1149:
1147:
1144:
1143:
1126:
1122:
1113:
1109:
1094:
1090:
1084:
1080:
1078:
1075:
1074:
1042:
1039:
1038:
1018:
1014:
999:
995:
980:
976:
974:
971:
970:
947:
943:
941:
938:
937:
920:
916:
895:
891:
882:
878:
876:
873:
872:
847:
843:
841:
838:
837:
810:
806:
804:
801:
800:
783:
779:
764:
760:
754:
750:
748:
745:
744:
712:
709:
708:
692:
689:
688:
649:
646:
645:
626:
623:
622:
586:
583:
582:
559:
556:
555:
533:
530:
529:
524:output alphabet
507:
504:
503:
477:
474:
473:
419:
416:
415:
403:
395:electronic lock
371:formal language
356:output alphabet
352:output function
295:
283:
230:formal grammars
210:Edward F. Moore
155:finite automata
151:
118:formal language
74:Automata theory
68:
64:
60:
47:
46:
45:
44:
41:
37:
33:
24:
17:
12:
11:
5:
6657:
6647:
6646:
6629:
6628:
6626:
6625:
6612:
6604:
6601:
6600:
6598:
6597:
6592:
6587:
6582:
6581:
6580:
6569:
6567:
6563:
6562:
6560:
6559:
6553:
6551:
6547:
6546:
6544:
6543:
6536:
6531:
6526:
6521:
6515:
6513:
6509:
6508:
6506:
6505:
6500:
6495:
6490:
6485:
6480:
6475:
6469:
6467:
6461:
6460:
6457:
6456:
6454:
6453:
6448:
6443:
6438:
6433:
6428:
6423:
6418:
6413:
6407:
6405:
6396:
6395:
6394:
6393:
6388:
6378:
6377:
6376:
6371:
6361:
6356:
6355:
6354:
6344:
6343:
6342:
6337:
6332:
6327:
6322:
6317:
6312:
6302:
6301:
6300:
6295:
6284:
6282:
6274:
6273:
6271:
6270:
6265:
6260:
6251:
6240:
6238:
6232:
6231:
6229:
6228:
6223:
6222:
6221:
6216:
6211:
6206:
6196:
6195:
6194:
6189:
6184:
6179:
6169:
6168:
6167:
6162:
6157:
6152:
6142:
6141:
6140:
6130:
6129:
6128:
6123:
6113:
6112:
6111:
6109:Control theory
6106:
6096:
6095:
6094:
6089:
6084:
6074:
6073:
6072:
6067:
6062:
6052:
6051:
6050:
6040:
6034:
6032:
6026:
6025:
6023:
6022:
6017:
6012:
6007:
6002:
5996:
5994:
5988:
5987:
5984:
5983:
5981:
5980:
5975:
5970:
5965:
5960:
5955:
5950:
5945:
5940:
5934:
5932:
5923:
5922:
5917:
5912:
5907:
5902:
5901:
5900:
5890:
5885:
5880:
5875:
5870:
5869:
5868:
5863:
5852:
5850:
5844:
5843:
5836:
5835:
5828:
5821:
5813:
5804:
5803:
5801:
5800:
5790:
5780:
5769:
5766:
5765:
5763:
5762:
5757:
5752:
5747:
5742:
5737:
5732:
5727:
5722:
5717:
5712:
5707:
5702:
5697:
5692:
5687:
5682:
5677:
5672:
5667:
5661:
5659:
5655:
5654:
5652:
5651:
5649:Solid modeling
5646:
5641:
5636:
5631:
5626:
5621:
5616:
5610:
5608:
5602:
5601:
5599:
5598:
5593:
5588:
5583:
5578:
5572:
5570:
5564:
5563:
5561:
5560:
5555:
5550:
5548:Control method
5545:
5540:
5535:
5530:
5525:
5519:
5517:
5511:
5510:
5508:
5507:
5502:
5500:Multithreading
5497:
5492:
5487:
5481:
5479:
5473:
5472:
5470:
5469:
5464:
5459:
5454:
5449:
5443:
5441:
5435:
5434:
5432:
5431:
5426:
5421:
5416:
5411:
5406:
5401:
5396:
5394:Formal methods
5391:
5385:
5383:
5377:
5376:
5374:
5373:
5368:
5366:World Wide Web
5363:
5358:
5353:
5348:
5343:
5338:
5333:
5328:
5323:
5318:
5313:
5308:
5302:
5300:
5294:
5293:
5291:
5290:
5285:
5280:
5275:
5270:
5265:
5260:
5255:
5249:
5247:
5240:
5239:
5237:
5236:
5231:
5226:
5221:
5216:
5210:
5208:
5202:
5201:
5199:
5198:
5193:
5188:
5183:
5178:
5173:
5168:
5167:
5166:
5155:
5153:
5147:
5146:
5144:
5143:
5138:
5133:
5128:
5123:
5118:
5113:
5108:
5103:
5098:
5092:
5090:
5084:
5083:
5081:
5080:
5075:
5070:
5065:
5060:
5055:
5050:
5045:
5040:
5035:
5029:
5027:
5017:
5016:
5014:
5013:
5008:
5003:
4998:
4993:
4987:
4985:
4981:
4980:
4978:
4977:
4972:
4967:
4962:
4957:
4952:
4946:
4944:
4938:
4937:
4935:
4934:
4929:
4924:
4919:
4914:
4908:
4906:
4902:
4901:
4899:
4898:
4889:
4884:
4879:
4874:
4869:
4864:
4859:
4854:
4849:
4843:
4841:
4835:
4834:
4827:
4824:
4823:
4816:
4815:
4808:
4801:
4793:
4784:
4783:
4771:
4768:
4767:
4763:
4762:
4760:
4759:
4757:Acyclic finite
4754:
4749:
4744:
4739:
4734:
4729:
4724:
4718:
4713:
4708:
4707:Turing Machine
4702:
4700:Linear-bounded
4697:
4692:
4690:Turing machine
4686:
4684:
4682:
4681:
4676:
4671:
4666:
4661:
4656:
4651:
4649:Tree-adjoining
4646:
4641:
4638:
4633:
4625:
4620:
4615:
4609:
4607:
4605:
4604:
4599:
4596:
4591:
4586:
4581:
4576:
4574:Tree-adjoining
4571:
4566:
4563:
4558:
4550:
4545:
4542:
4536:
4534:
4532:
4531:
4528:
4525:
4522:
4519:
4516:
4513:
4510:
4507:
4504:
4501:
4498:
4495:
4492:
4488:
4485:
4484:
4479:
4474:
4469:
4461:
4458:
4457:
4442:
4441:
4434:
4427:
4419:
4413:
4412:
4407:
4400:
4399:External links
4397:
4396:
4395:
4389:
4376:
4360:
4354:
4338:
4322:
4308:
4291:
4265:
4241:
4227:
4210:
4196:
4172:
4166:
4148:
4141:
4127:Michael Sipser
4123:
4117:
4099:Rajeev Motwani
4089:
4086:
4083:
4082:
4066:
4053:
4041:
4034:
4013:
3996:
3957:
3917:
3910:
3890:
3869:
3851:
3833:
3806:
3781:(2): 114–125.
3760:Rabin, Michael
3751:
3715:
3689:(3): 113–124.
3663:
3648:
3624:
3609:
3552:
3545:
3527:
3504:
3503:
3501:
3498:
3497:
3496:
3491:
3484:
3481:
3447:
3443:
3439:
3434:
3430:
3409:Norbert Wiener
3401:
3400:
3384:
3361:
3352:
3317:
3314:
3303:
3300:
3284:Edward Fredkin
3235:
3232:
3229:
3228:
3211:
3206:
3179:
3174:
3147:
3142:
3115:
3110:
3083:
3078:
3049:
3044:
3016:
2991:
2964:
2936:
2908:
2903:
2884:
2883:
2873:
2870:
2849:
2846:
2843:
2842:
2840:
2834:
2833:
2815:
2814:
2809:
2805:
2804:
2799:
2795:Deterministic
2792:
2791:
2786:
2784:Turing machine
2780:
2779:
2774:
2767:
2766:
2761:
2754:
2753:
2748:
2741:
2740:
2735:
2728:
2727:
2724:
2714:
2711:
2710:
2709:
2702:
2699:
2688:
2687:
2684:
2677:
2667:
2666:
2644:
2634:
2627:
2626:
2622:
2621:
2614:Turing machine
2607:
2583:
2569:
2556:
2555:
2551:
2550:
2539:Turing machine
2524:
2508:
2492:
2482:
2476:
2461:
2460:
2456:
2455:
2445:
2442:tree automaton
2438:makes one copy
2421:
2408:Infinite input
2405:
2398:
2397:
2388:
2385:
2384:
2383:
2368:
2364:
2363:
2351:
2348:
2345:
2342:
2339:
2336:
2331:
2327:
2323:
2318:
2315:
2306:
2297:
2293:
2289:
2286:
2283:
2280:
2277:
2252:
2248:
2244:
2241:
2230:
2226:
2225:
2213:
2193:
2190:
2187:
2184:
2181:
2176:
2172:
2168:
2163:
2160:
2147:accepting word
2132:
2128:
2124:
2119:
2115:
2111:
2108:
2105:
2100:
2096:
2090:
2086:
2082:
2079:
2068:
2067:Accepting word
2064:
2063:
2060:
2059:
2058:
2042:
2039:
2036:
2016:
1996:
1986:
1970:
1967:
1962:
1958:
1935:
1915:
1895:
1894:
1891:
1879:
1859:
1839:
1836:
1833:
1830:
1827:
1822:
1819:
1797:
1777:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1751:
1748:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1714:
1711:
1689:
1669:
1649:
1646:
1626:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1583:
1580:
1558:
1538:
1535:
1530:
1526:
1522:
1519:
1516:
1511:
1508:
1486:
1474:
1473:
1461:
1456:
1452:
1448:
1443:
1440:
1437:
1433:
1429:
1426:
1404:
1400:
1373:
1369:
1348:
1343:
1339:
1335:
1330:
1327:
1324:
1320:
1316:
1313:
1291:
1287:
1264:
1260:
1237:
1233:
1210:
1206:
1183:
1179:
1156:
1152:
1129:
1125:
1121:
1116:
1112:
1108:
1105:
1102:
1097:
1093:
1087:
1083:
1058:
1055:
1052:
1049:
1046:
1026:
1021:
1017:
1013:
1008:
1005:
1002:
998:
994:
991:
988:
983:
979:
958:
955:
950:
946:
923:
919:
915:
912:
909:
906:
903:
898:
894:
890:
885:
881:
869:
865:
864:
850:
846:
821:
818:
813:
809:
786:
782:
778:
775:
772:
767:
763:
757:
753:
737:
733:
732:
716:
696:
685:
684:
683:
671:
668:
665:
662:
659:
656:
653:
630:
620:
608:
605:
602:
599:
596:
593:
590:
563:
553:
537:
527:
511:
501:
498:input alphabet
481:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
408:
407:
402:
399:
375:starting state
294:
291:
282:
279:
224:described the
194:Claude Shannon
179:Turing machine
159:systems theory
150:
147:
66:
62:
58:
40:
38:
22:
21:
20:
15:
9:
6:
4:
3:
2:
6656:
6645:
6642:
6641:
6639:
6624:
6620:
6616:
6613:
6611:
6610:
6606:
6605:
6602:
6596:
6593:
6591:
6588:
6586:
6583:
6579:
6576:
6575:
6574:
6571:
6570:
6568:
6566:Organizations
6564:
6558:
6555:
6554:
6552:
6548:
6541:
6537:
6535:
6532:
6530:
6527:
6525:
6522:
6520:
6517:
6516:
6514:
6510:
6504:
6501:
6499:
6496:
6494:
6491:
6489:
6486:
6484:
6481:
6479:
6476:
6474:
6471:
6470:
6468:
6466:
6462:
6452:
6449:
6447:
6444:
6442:
6439:
6437:
6434:
6432:
6429:
6427:
6426:Quantum group
6424:
6422:
6419:
6417:
6414:
6412:
6409:
6408:
6406:
6404:
6400:
6392:
6389:
6387:
6384:
6383:
6382:
6381:Supersymmetry
6379:
6375:
6372:
6370:
6367:
6366:
6365:
6364:String theory
6362:
6360:
6357:
6353:
6350:
6349:
6348:
6345:
6341:
6338:
6336:
6333:
6331:
6328:
6326:
6323:
6321:
6318:
6316:
6313:
6311:
6308:
6307:
6306:
6303:
6299:
6296:
6294:
6291:
6290:
6289:
6286:
6285:
6283:
6281:
6275:
6269:
6266:
6264:
6263:Path integral
6261:
6259:
6255:
6252:
6249:
6245:
6244:Distributions
6242:
6241:
6239:
6237:
6233:
6227:
6224:
6220:
6217:
6215:
6212:
6210:
6207:
6205:
6202:
6201:
6200:
6197:
6193:
6190:
6188:
6185:
6183:
6180:
6178:
6175:
6174:
6173:
6170:
6166:
6163:
6161:
6158:
6156:
6153:
6151:
6148:
6147:
6146:
6143:
6139:
6136:
6135:
6134:
6131:
6127:
6124:
6122:
6119:
6118:
6117:
6114:
6110:
6107:
6105:
6102:
6101:
6100:
6097:
6093:
6090:
6088:
6085:
6083:
6080:
6079:
6078:
6075:
6071:
6068:
6066:
6063:
6061:
6058:
6057:
6056:
6053:
6049:
6046:
6045:
6044:
6041:
6039:
6036:
6035:
6033:
6031:
6027:
6021:
6018:
6016:
6013:
6011:
6010:Combinatorics
6008:
6006:
6003:
6001:
5998:
5997:
5995:
5993:
5989:
5979:
5976:
5974:
5971:
5969:
5966:
5964:
5961:
5959:
5956:
5954:
5951:
5949:
5946:
5944:
5941:
5939:
5936:
5935:
5933:
5931:
5927:
5921:
5918:
5916:
5913:
5911:
5908:
5906:
5903:
5899:
5896:
5895:
5894:
5891:
5889:
5886:
5884:
5883:Coding theory
5881:
5879:
5876:
5874:
5871:
5867:
5864:
5862:
5859:
5858:
5857:
5854:
5853:
5851:
5849:
5848:Computational
5845:
5841:
5834:
5829:
5827:
5822:
5820:
5815:
5814:
5811:
5799:
5791:
5789:
5781:
5779:
5771:
5770:
5767:
5761:
5758:
5756:
5753:
5751:
5748:
5746:
5743:
5741:
5738:
5736:
5733:
5731:
5728:
5726:
5723:
5721:
5718:
5716:
5713:
5711:
5708:
5706:
5703:
5701:
5698:
5696:
5693:
5691:
5688:
5686:
5683:
5681:
5678:
5676:
5673:
5671:
5668:
5666:
5663:
5662:
5660:
5656:
5650:
5647:
5645:
5642:
5640:
5637:
5635:
5634:Mixed reality
5632:
5630:
5627:
5625:
5622:
5620:
5617:
5615:
5612:
5611:
5609:
5607:
5603:
5597:
5594:
5592:
5589:
5587:
5584:
5582:
5579:
5577:
5574:
5573:
5571:
5569:
5565:
5559:
5556:
5554:
5551:
5549:
5546:
5544:
5541:
5539:
5536:
5534:
5531:
5529:
5526:
5524:
5521:
5520:
5518:
5516:
5512:
5506:
5503:
5501:
5498:
5496:
5493:
5491:
5488:
5486:
5483:
5482:
5480:
5478:
5474:
5468:
5467:Accessibility
5465:
5463:
5462:Visualization
5460:
5458:
5455:
5453:
5450:
5448:
5445:
5444:
5442:
5440:
5436:
5430:
5427:
5425:
5422:
5420:
5417:
5415:
5412:
5410:
5407:
5405:
5402:
5400:
5397:
5395:
5392:
5390:
5387:
5386:
5384:
5382:
5378:
5372:
5369:
5367:
5364:
5362:
5359:
5357:
5354:
5352:
5349:
5347:
5344:
5342:
5339:
5337:
5334:
5332:
5329:
5327:
5324:
5322:
5319:
5317:
5314:
5312:
5309:
5307:
5304:
5303:
5301:
5299:
5295:
5289:
5286:
5284:
5281:
5279:
5276:
5274:
5271:
5269:
5266:
5264:
5261:
5259:
5256:
5254:
5251:
5250:
5248:
5246:
5241:
5235:
5232:
5230:
5227:
5225:
5222:
5220:
5217:
5215:
5212:
5211:
5209:
5207:
5203:
5197:
5194:
5192:
5189:
5187:
5184:
5182:
5179:
5177:
5174:
5172:
5169:
5165:
5162:
5161:
5160:
5157:
5156:
5154:
5152:
5148:
5142:
5139:
5137:
5134:
5132:
5129:
5127:
5124:
5122:
5119:
5117:
5114:
5112:
5109:
5107:
5104:
5102:
5099:
5097:
5094:
5093:
5091:
5089:
5085:
5079:
5076:
5074:
5071:
5069:
5066:
5064:
5061:
5059:
5056:
5054:
5051:
5049:
5046:
5044:
5041:
5039:
5036:
5034:
5031:
5030:
5028:
5026:
5022:
5018:
5012:
5009:
5007:
5004:
5002:
4999:
4997:
4994:
4992:
4989:
4988:
4986:
4982:
4976:
4973:
4971:
4968:
4966:
4963:
4961:
4958:
4956:
4953:
4951:
4948:
4947:
4945:
4943:
4939:
4933:
4930:
4928:
4925:
4923:
4922:Dependability
4920:
4918:
4915:
4913:
4910:
4909:
4907:
4903:
4897:
4893:
4890:
4888:
4885:
4883:
4880:
4878:
4875:
4873:
4870:
4868:
4865:
4863:
4860:
4858:
4855:
4853:
4850:
4848:
4845:
4844:
4842:
4840:
4836:
4831:
4825:
4821:
4814:
4809:
4807:
4802:
4800:
4795:
4794:
4791:
4776:
4775:proper subset
4769:
4758:
4755:
4753:
4750:
4748:
4745:
4743:
4740:
4738:
4735:
4733:
4730:
4728:
4725:
4723:
4719:
4717:
4714:
4712:
4709:
4706:
4703:
4701:
4698:
4696:
4693:
4691:
4688:
4687:
4685:
4680:
4677:
4675:
4672:
4670:
4667:
4665:
4662:
4660:
4657:
4655:
4652:
4650:
4647:
4645:
4642:
4639:
4637:
4634:
4631:
4626:
4624:
4621:
4619:
4616:
4614:
4611:
4610:
4608:
4603:
4602:Non-recursive
4600:
4597:
4595:
4592:
4590:
4587:
4585:
4582:
4580:
4577:
4575:
4572:
4570:
4567:
4564:
4562:
4559:
4556:
4551:
4549:
4546:
4543:
4541:
4538:
4537:
4535:
4529:
4526:
4523:
4520:
4517:
4514:
4511:
4508:
4505:
4502:
4499:
4496:
4493:
4490:
4489:
4487:
4486:
4483:
4480:
4478:
4475:
4473:
4470:
4468:
4465:
4464:
4459:
4455:
4451:
4447:
4440:
4435:
4433:
4428:
4426:
4421:
4420:
4417:
4411:
4408:
4406:
4403:
4402:
4392:
4386:
4382:
4377:
4372:
4371:
4365:
4364:Marvin Minsky
4361:
4357:
4351:
4347:
4343:
4339:
4335:
4331:
4327:
4323:
4319:
4315:
4311:
4305:
4301:
4297:
4292:
4290:
4287:
4284:
4283:0-19-853424-8
4280:
4277:
4273:
4269:
4268:John M. Howie
4266:
4262:
4258:
4254:
4250:
4246:
4242:
4238:
4234:
4230:
4224:
4220:
4216:
4211:
4207:
4203:
4199:
4193:
4189:
4184:
4183:
4177:
4176:Salomaa, Arto
4173:
4169:
4163:
4159:
4158:
4153:
4149:
4144:
4138:
4134:
4133:
4128:
4124:
4120:
4114:
4110:
4109:
4104:
4100:
4096:
4092:
4091:
4079:
4076:
4070:
4063:
4057:
4050:
4045:
4037:
4031:
4027:
4023:
4017:
4010:
4006:
4000:
3992:
3988:
3984:
3980:
3976:
3972:
3968:
3961:
3954:
3950:
3946:
3942:
3937:
3932:
3928:
3921:
3913:
3907:
3903:
3902:
3894:
3885:
3880:
3873:
3862:
3855:
3844:
3837:
3829:
3825:
3824:Stearns, R.E.
3821:
3820:Hartmanis, J.
3815:
3813:
3811:
3802:
3796:
3788:
3784:
3780:
3776:
3769:
3765:
3761:
3755:
3746:
3741:
3737:
3733:
3729:
3725:
3719:
3708:
3704:
3700:
3696:
3692:
3688:
3684:
3677:
3673:
3672:Chomsky, Noam
3667:
3659:
3652:
3644:
3637:
3635:
3633:
3631:
3629:
3620:
3613:
3598:on 2023-06-04
3594:
3590:
3586:
3582:
3578:
3575:(2): 95–104.
3574:
3570:
3563:
3556:
3548:
3546:0-471-08848-X
3542:
3538:
3531:
3516:
3509:
3505:
3495:
3492:
3490:
3487:
3486:
3480:
3478:
3474:
3470:
3466:
3465:
3445:
3441:
3432:
3428:
3419:
3416:
3415:
3410:
3406:
3398:
3397:
3396:
3394:
3390:
3383:
3379:
3378:
3373:
3369:
3364:
3360:
3355:
3351:
3347:
3343:
3339:
3335:
3331:
3327:
3323:
3313:
3310:
3299:
3297:
3293:
3290:: the set of
3289:
3288:finite fields
3285:
3281:
3277:
3273:
3269:
3265:
3261:
3257:
3253:
3249:
3245:
3241:
3227:
3226:
3194:
3162:
3130:
3098:
3064:
3030:
3014:
3005:
2989:
2978:
2962:
2951:
2934:
2924:
2889:
2886:
2885:
2881:
2880:
2877:
2869:
2867:
2863:
2859:
2855:
2841:
2839:
2836:
2835:
2832:
2828:
2824:
2820:
2817:
2816:
2813:
2807:
2806:
2803:
2800:
2798:
2794:
2793:
2790:
2787:
2785:
2782:
2781:
2778:
2775:
2772:
2769:
2768:
2765:
2762:
2759:
2756:
2755:
2752:
2749:
2746:
2743:
2742:
2739:
2736:
2733:
2730:
2729:
2725:
2722:
2721:
2718:
2707:
2703:
2700:
2697:
2696:
2695:
2693:
2685:
2682:
2678:
2675:
2674:
2673:
2670:
2664:
2660:
2656:
2652:
2648:
2645:
2642:
2638:
2635:
2632:
2629:
2628:
2624:
2623:
2619:
2615:
2611:
2608:
2605:
2601:
2600:
2595:
2591:
2587:
2584:
2581:
2577:
2573:
2570:
2567:
2566:
2561:
2560:Deterministic
2558:
2557:
2553:
2552:
2548:
2544:
2540:
2536:
2535:working tapes
2532:
2528:
2525:
2522:
2521:
2520:queue machine
2516:
2512:
2509:
2506:
2505:
2500:
2496:
2493:
2490:
2486:
2483:
2480:
2479:Finite states
2477:
2474:
2470:
2466:
2463:
2462:
2458:
2457:
2453:
2449:
2446:
2443:
2439:
2435:
2431:
2430:
2425:
2422:
2419:
2418:
2413:
2409:
2406:
2403:
2400:
2399:
2395:
2394:
2393:
2381:
2377:
2373:
2369:
2366:
2365:
2346:
2343:
2337:
2334:
2329:
2325:
2313:
2295:
2287:
2284:
2278:
2275:
2267:
2250:
2242:
2239:
2232:The language
2231:
2228:
2227:
2211:
2191:
2188:
2182:
2179:
2174:
2170:
2158:
2148:
2130:
2122:
2117:
2113:
2109:
2106:
2103:
2098:
2094:
2088:
2084:
2080:
2077:
2069:
2066:
2065:
2061:
2056:
2055:accept states
2040:
2037:
2034:
2014:
1994:
1987:
1984:
1968:
1965:
1960:
1956:
1948:
1947:
1933:
1905:
1901:
1897:
1896:
1892:
1877:
1857:
1834:
1831:
1828:
1817:
1795:
1772:
1769:
1763:
1760:
1757:
1746:
1738:
1735:
1729:
1726:
1723:
1720:
1709:
1687:
1667:
1647:
1644:
1624:
1604:
1601:
1595:
1592:
1589:
1578:
1556:
1536:
1528:
1520:
1517:
1514:
1506:
1484:
1476:
1475:
1454:
1450:
1446:
1441:
1438:
1435:
1431:
1424:
1402:
1398:
1389:
1371:
1367:
1341:
1337:
1333:
1328:
1325:
1322:
1318:
1311:
1289:
1285:
1262:
1258:
1235:
1231:
1208:
1204:
1181:
1177:
1154:
1150:
1127:
1119:
1114:
1110:
1106:
1103:
1100:
1095:
1091:
1085:
1081:
1072:
1056:
1053:
1050:
1047:
1044:
1019:
1015:
1011:
1006:
1003:
1000:
996:
989:
986:
981:
977:
956:
953:
948:
944:
921:
917:
913:
910:
907:
904:
901:
896:
892:
888:
883:
879:
870:
867:
866:
848:
835:
816:
811:
807:
784:
780:
776:
773:
770:
765:
761:
755:
751:
742:
738:
735:
734:
730:
714:
694:
686:
660:
657:
654:
651:
644:
628:
621:
606:
597:
594:
591:
588:
581:
577:
561:
554:
551:
535:
528:
525:
502:
499:
496:, called the
495:
472:
471:
454:
451:
448:
445:
442:
439:
433:
424:
421:
414:
410:
409:
405:
404:
398:
396:
392:
388:
384:
380:
377:and a set of
376:
372:
367:
365:
361:
357:
353:
349:
346:) based on a
345:
341:
337:
333:
329:
328:
322:
318:
317:
312:
308:
304:
300:
297:An automaton
290:
288:
278:
276:
272:
266:
264:
260:
256:
252:
248:
245:The study of
243:
241:
237:
236:
231:
227:
223:
219:
215:
211:
207:
206:Marvin Minsky
203:
199:
198:W. Ross Ashby
195:
191:
186:
184:
180:
176:
172:
168:
164:
160:
156:
146:
144:
140:
136:
132:
128:
124:
119:
114:
112:
108:
104:
99:
95:
91:
87:
83:
79:
75:
56:
55:state diagram
51:
19:
6621: /
6617: /
6607:
6483:Optimization
6446:Superalgebra
6305:Field theory
6278:Mathematical
6256: /
6104:Chaos theory
6087:Gauge theory
6015:Graph theory
5910:Cryptography
5872:
5730:Cyberwarfare
5389:Cryptography
5175:
4711:Nested stack
4654:Context-free
4579:Context-free
4540:Unrestricted
4445:
4380:
4369:
4345:
4333:
4295:
4271:
4248:
4245:Conway, J.H.
4214:
4181:
4156:
4131:
4107:
4077:
4074:
4069:
4061:
4056:
4044:
4025:
4016:
4008:
4005:Věra Trnková
3999:
3977:(4): 59–70.
3974:
3970:
3960:
3926:
3920:
3900:
3893:
3872:
3854:
3836:
3827:
3795:cite journal
3778:
3774:
3766:(Apr 1959).
3754:
3735:
3731:
3718:
3686:
3682:
3666:
3657:
3651:
3642:
3618:
3612:
3600:. Retrieved
3593:the original
3572:
3568:
3555:
3536:
3530:
3519:. Retrieved
3508:
3461:
3417:
3412:
3404:
3402:
3381:
3376:
3375:
3367:
3362:
3358:
3353:
3349:
3333:
3329:
3319:
3305:
3276:Game of Life
3242:are used in
3237:
3234:Applications
2892:
2875:
2865:
2851:
2716:
2706:Minimization
2689:
2680:
2671:
2668:
2646:
2640:
2636:
2630:
2609:
2603:
2597:
2593:
2589:
2585:
2579:
2575:
2571:
2563:
2559:
2534:
2530:
2526:
2518:
2511:Queue memory
2510:
2502:
2495:Stack memory
2494:
2484:
2478:
2468:
2465:Single state
2464:
2447:
2437:
2433:
2427:
2423:
2415:
2407:
2402:Finite input
2401:
2390:
2375:
2265:
2146:
2054:
1982:
1903:
1390:of the run,
1387:
1070:
833:
642:
579:
575:
549:
548:is a set of
523:
497:
493:
390:
386:
382:
378:
374:
368:
363:
359:
355:
351:
347:
343:
339:
335:
331:
324:
320:
314:
310:
306:
302:
298:
296:
284:
267:
244:
233:
222:Noam Chomsky
189:
187:
169:rather than
165:to describe
152:
115:
97:
73:
72:
18:
6623:topics list
6557:Mathematics
6473:Game theory
6374:Topological
6340:Topological
6335:Statistical
6298:Hamiltonian
5740:Video games
5720:Digital art
5477:Concurrency
5346:Data mining
5258:Probability
4991:Interpreter
4720:restricted
4160:. Pearson.
4152:Elaine Rich
3971:ACM Inroads
3764:Scott, Dana
3280:Konrad Zuse
3272:John Conway
2651:probability
2641:ω-automaton
2610:Two-wayness
2586:Alternation
2527:Tape memory
1983:start state
1870:from state
1388:final state
743:of symbols
364:final state
344:transitions
249:led to the
96:. The word
6529:Psychology
6493:Statistics
6293:Lagrangian
5920:Statistics
5856:Algorithms
5798:Glossaries
5670:E-commerce
5263:Statistics
5206:Algorithms
5164:Stochastic
4996:Middleware
4852:Peripheral
4318:1188.68177
4261:0231.94041
4237:1127.68049
4206:0565.68046
3936:1701.06040
3884:1907.12713
3738:(4): 541.
3724:Nerode, A.
3602:2021-03-29
3521:2020-06-07
3500:References
3477:2-category
3322:categories
3065:(NPDA-II)
3031:(DPDA-II)
2882:Automaton
2723:Automaton
2424:Tree input
2417:ω-automata
2266:recognized
969:such that
834:input word
736:Input word
307:time steps
263:Dana Scott
240:set theory
6534:Sociology
6524:Chemistry
6320:Effective
6315:Conformal
6310:Classical
6182:Geometric
6155:Geometric
5619:Rendering
5614:Animation
5245:computing
5196:Semantics
4887:Processor
4674:Star-free
4628:Positive
4618:Decidable
4553:Positive
4477:Languages
3494:Petri net
3438:→
3372:semigroup
3015:∩
2990:∩
2979:(NPDA-I)
2963:∩
2952:(DPDA-I)
2935:∩
2489:countable
2344:∈
2317:¯
2314:δ
2296:∗
2292:Σ
2288:∈
2251:∗
2247:Σ
2243:⊆
2189:∈
2162:¯
2159:δ
2131:∗
2127:Σ
2123:∈
2053:) called
2038:⊆
1966:∈
1934:λ
1914:Γ
1821:¯
1818:λ
1796:λ
1750:¯
1747:δ
1739:δ
1713:¯
1710:δ
1596:ε
1582:¯
1579:δ
1557:ε
1534:→
1529:∗
1525:Σ
1521:×
1510:¯
1507:δ
1485:δ
1439:−
1425:λ
1326:−
1312:δ
1128:∗
1124:Σ
1120:∈
1054:≤
1004:−
990:δ
954:∈
849:∗
845:Σ
820:Σ
817:∈
670:Γ
667:→
664:Σ
661:×
652:λ
629:λ
604:→
601:Σ
598:×
589:δ
562:δ
510:Γ
480:Σ
470:, where:
458:⟩
455:λ
449:δ
437:Γ
431:Σ
428:⟨
413:quintuple
406:Automaton
309:(or just
6638:Category
6609:Category
6258:analysis
6177:Exterior
6150:Exterior
6030:Analysis
5992:Discrete
5866:analysis
5778:Category
5606:Graphics
5381:Security
5043:Compiler
4942:Networks
4839:Hardware
4472:Grammars
4366:(1967).
4332:(1995).
4247:(1971).
4178:(1985).
4154:(2008).
4129:(1997).
4105:(2000).
4080::105–155
4024:(1971).
4007:. 1990.
3826:(1966).
3726:(1958).
3707:Archived
3703:19519474
3674:(1956).
3483:See also
3464:groupoid
3346:colimits
1904:acceptor
1893:Acceptor
936:, where
799:, where
327:alphabet
281:Automata
98:automata
82:automata
6619:outline
6550:Related
6519:Biology
6369:Bosonic
6330:Quantum
6280:physics
6246: (
5978:Solvers
5788:Outline
4695:Decider
4669:Regular
4636:Indexed
4594:Regular
4561:Indexed
4289:1254435
4270:(1991)
3991:6446749
3953:3962424
3589:6060865
3389:Monoids
2747:(DPDA)
2592:on the
2412:ω-words
2070:A word
1069:, is a
641:is the
574:is the
494:symbols
321:letters
316:symbols
149:History
139:parsing
6192:Vector
6187:Tensor
6165:Vector
6160:Tensor
5861:design
4747:Finite
4679:Finite
4524:Type-3
4515:Type-2
4497:Type-1
4491:Type-0
4387:
4352:
4316:
4306:
4281:
4259:
4235:
4225:
4204:
4194:
4164:
4139:
4115:
4032:
3989:
3951:
3908:
3701:
3587:
3543:
3370:or as
3342:limits
3195:(MTM)
3163:(PTM)
3131:(NTM)
3099:(DTM)
3006:(LBA)
2773:(LBA)
2760:(PDA)
2734:(FSM)
2681:closed
2604:copies
2545:, and
2459:States
2309:
2301:
2145:is an
2027:(i.e.
1660:where
1223:. For
741:string
550:states
387:reject
383:accept
336:states
325:input
303:inputs
287:system
212:, and
107:states
6325:Gauge
5191:Logic
5025:tools
4705:PTIME
4410:libfa
3987:S2CID
3949:S2CID
3931:arXiv
3879:arXiv
3864:(PDF)
3846:(PDF)
3771:(PDF)
3710:(PDF)
3699:S2CID
3679:(PDF)
3596:(PDF)
3565:(PDF)
2925:(NFA)
2860:, or
2639:: an
2531:tapes
2515:queue
2499:stack
2434:reads
2396:Input
1985:, and
1946:with
727:is a
360:halts
332:words
311:steps
5023:and
4896:Form
4892:Size
4452:and
4385:ISBN
4350:ISBN
4304:ISBN
4279:ISBN
4223:ISBN
4192:ISBN
4162:ISBN
4137:ISBN
4113:ISBN
4030:ISBN
3906:ISBN
3801:link
3585:PMID
3541:ISBN
3344:and
2661:and
2594:same
2370:The
1926:and
1048:<
1037:for
299:runs
261:and
141:and
80:and
4314:Zbl
4257:Zbl
4233:Zbl
4202:Zbl
3979:doi
3941:doi
3783:doi
3740:doi
3691:doi
3577:doi
3471:or
3418:via
3328:or
3274:'s
2866:and
2856:or
1071:run
868:Run
687:If
578:or
385:or
319:or
6640::
4894:/
4448::
4328:;
4312:.
4302:.
4286:MR
4274:,
4255:.
4231:.
4221:.
4200:.
4190:.
4101:;
4097:;
4078:88
3985:.
3973:.
3969:.
3947:,
3939:,
3822:;
3809:^
3797:}}
3793:{{
3777:.
3773:.
3762:;
3734:.
3730:.
3705:.
3697:.
3685:.
3681:.
3627:^
3583:.
3571:.
3567:.
3395:.
3387:.
3298:.
3262:.
3250:.
2829:,
2825:,
2821:,
2657:,
2541:,
1569:,
366:.
340:in
242:.
208:,
204:,
200:,
196:,
185:.
145:.
137:,
133:,
129:,
6542:"
6538:"
6250:)
5832:e
5825:t
5818:v
4832:.
4812:e
4805:t
4798:v
4640:—
4598:—
4565:—
4530:—
4527:—
4521:—
4518:—
4512:—
4509:—
4506:—
4503:—
4500:—
4494:—
4438:e
4431:t
4424:v
4393:.
4358:.
4320:.
4263:.
4239:.
4208:.
4170:.
4145:.
4121:.
4064:.
4038:.
3993:.
3981::
3975:2
3943::
3933::
3914:.
3887:.
3881::
3866:.
3848:.
3803:)
3785::
3779:3
3748:.
3742::
3736:9
3693::
3687:2
3605:.
3579::
3573:1
3549:.
3524:.
3446:i
3442:A
3433:i
3429:A
3385:g
3382:S
3377:S
3363:j
3359:A
3354:i
3350:A
3210:|
3205:|
3178:|
3173:|
3146:|
3141:|
3114:|
3109:|
3082:|
3077:|
3048:|
3043:|
2907:|
2902:|
2708:)
2620:.
2582:.
2568:.
2549:.
2507:.
2475:.
2454:.
2444:.
2420:.
2362:.
2350:}
2347:F
2341:)
2338:w
2335:,
2330:0
2326:q
2322:(
2305:|
2285:w
2282:{
2279:=
2276:L
2240:L
2212:w
2192:F
2186:)
2183:w
2180:,
2175:0
2171:q
2167:(
2118:n
2114:a
2110:.
2107:.
2104:.
2099:2
2095:a
2089:1
2085:a
2081:=
2078:w
2057:.
2041:Q
2035:F
2015:Q
1995:F
1969:Q
1961:0
1957:q
1890:.
1878:q
1858:w
1838:)
1835:w
1832:,
1829:q
1826:(
1776:)
1773:a
1770:,
1767:)
1764:w
1761:,
1758:q
1755:(
1742:(
1736:=
1733:)
1730:a
1727:w
1724:,
1721:q
1718:(
1688:w
1668:a
1648:a
1645:w
1625:q
1605:q
1602:=
1599:)
1593:,
1590:q
1587:(
1537:Q
1518:Q
1515::
1472:.
1460:)
1455:i
1451:a
1447:,
1442:1
1436:i
1432:q
1428:(
1403:n
1399:q
1372:n
1368:a
1347:)
1342:i
1338:a
1334:,
1329:1
1323:i
1319:q
1315:(
1290:i
1286:q
1263:i
1259:a
1236:1
1232:a
1209:1
1205:a
1182:0
1178:q
1155:0
1151:q
1115:n
1111:a
1107:.
1104:.
1101:.
1096:2
1092:a
1086:1
1082:a
1057:n
1051:i
1045:0
1025:)
1020:i
1016:a
1012:,
1007:1
1001:i
997:q
993:(
987:=
982:i
978:q
957:Q
949:i
945:q
922:n
918:q
914:,
911:.
908:.
905:.
902:,
897:1
893:q
889:,
884:0
880:q
863:.
812:i
808:a
785:n
781:a
777:.
774:.
771:.
766:2
762:a
756:1
752:a
731:.
715:M
695:Q
658:Q
655::
607:Q
595:Q
592::
552:,
536:Q
452:,
446:,
443:Q
440:,
434:,
425:=
422:M
67:1
63:1
59:1
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
