# 自动机理论

The study of the mathematical properties of such automata is automata theory. The picture is a visualization of an automaton that recognizes strings containing an even number of 0s. The automaton starts in state S1, and transitions to the non-accepting state S2 upon reading the symbol 0. Reading another 0 causes the automaton to transition back to the accepting state S1. In both states the symbol 1 is ignored by making a transition to the current state.

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means "self-making".

“自动机理论”是对抽象机器自动机以及使用它们可以解决的计算性问题的研究。它是[[理论计算机科学]中的一个理论。“automata”一词（automata的复数形式）来自希腊语单词αὐτόματα，意思是“自我创造”。

The study of the mathematical properties of such automata is automata theory. The picture is a visualization of an automaton that recognizes strings containing an even number of 0s. The automaton starts in state S1, and transitions to the non-accepting state S2 upon reading the symbol 0. Reading another 0 causes the automaton to transition back to the accepting state S1. In both states the symbol 1 is ignored by making a transition to the current state.

The figure at right illustrates a finite-state machine, which belongs to a well-known type of automaton. This automaton consists of states (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 transition function, which takes the current state and the recent symbol as its inputs.

Automata theory is closely related to formal language theory. An automaton is a finite representation of a formal language that may be an infinite set. Automata are often classified by the class of formal languages they can recognize, typically illustrated by the Chomsky hierarchy, which describes the relations between various languages and kinds of formalized logics.

Automata play a major role in theory of computation, compiler construction, artificial intelligence, parsing and formal verification.

Automata play a major role in theory of computation, compiler construction, artificial intelligence, parsing and formal verification.

## Automata自动机

Following is an introductory definition of one type of automaton, which attempts to help one grasp the essential concepts involved in automata theory/theories.

### Very informal description非常非正式的描述

An automaton is a construct made of states designed to determine if the input should be accepted or rejected. It looks a lot like a basic board game where each space on the board represents a state. Each state has information about what to do when an input is received by the machine (again, rather like what to do when you land on the Go To Jail spot in a popular board game). As the machine receives a new input, it looks at the state and picks a new spot based on the information on what to do when it receives that input at that state. When there are no more inputs, the automaton stops and the space it is on when it completes determines whether the automaton accepts or rejects that particular set of inputs.

### Informal description非正式的描述

An automaton runs when it is given some sequence of inputs in discrete (individual) time steps or steps. An automaton processes one input picked from a set of symbols or letters, which is called an alphabet. The symbols received by the automaton as input at any step are a finite sequence of symbols called words. An automaton has a finite set of states. At each moment during a run of the automaton, the automaton is in one of its states. When the automaton receives new input it moves to another state (or transitions) based on a function that takes the current state and symbol as parameters. This function is called the transition function. The automaton reads the symbols of the input word one after another and transitions from state to state according to the transition function until the word is read completely. Once the input word has been read, the automaton is said to have stopped. The state at which the automaton stops is called the final state. Depending on the final state, it's said that the automaton either accepts or rejects an input word. There is a subset of states of the automaton, which is defined as the set of accepting states. If the final state is an accepting state, then the automaton accepts the word. Otherwise, the word is rejected. The set of all the words accepted by an automaton is called the language recognized by the automaton.

In short, an automaton is a mathematical object that takes a word as input and decides whether to accept it or reject it. Since all computational problems are reducible into the accept/reject question on inputs, (all problem instances can be represented in a finite length of symbols)[citation needed], automata theory plays a crucial role in computational theory.

### Formal definition正式的描述

Automaton

Automaton

#### definition of finite state automata有限状态自动机的定义

A deterministic finite automaton is represented formally by a 5-tuple 模板:Not a typo, where:

• Q is a finite set of states.
• Q 是状态的有限集合。
• Σ是一个有限的符号集，称为自动机字母表。
• δ is the transition function, that is, δ: Q × Σ → Q.
• δ 是跃迁函数，即 δ: q × σ → q。
• q0 is the start state, that is, the state of the automaton before any input has been processed, where q0∈ Q.
• q0 是起始状态，即自动机在任意输入被处理之前的状态，其中 q0∈ Q。
• F is a set of states of Q (i.e. F⊆Q) called accept states.
• F 是 Q (i.e. F⊆Q) 的一组状态称为“接受状态”。

Input word

Input word

An automaton reads a finite string of symbols a1,a2,...., an , where ai ∈ Σ, which is called an input word. The set of all words is denoted by Σ*.

Run

Run

A sequence of states q0,q1,q2,...., qn, where qi ∈ Q such that q0 is the start state and qi = δ(qi-1,ai) for 0 < i ≤ n, is a run of the automaton on an input word w = a1,a2,...., an ∈ Σ*. In other words, at first the automaton is at the start state q0, and then the automaton reads symbols of the input word in sequence. When the automaton reads symbol ai it jumps to state qi = δ(qi-1,ai). qn is said to be the final state of the run.

Accepting word

Accepting word

A word w ∈ Σ* is accepted by the automaton if qn ∈ F.

Recognized language

Recognized language

An automaton can recognize a formal language. The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton.

Recognizable languages

Recognizable languages

The recognizable languages are the set of languages that are recognized by some automaton. For the above definition of automata the recognizable languages are regular languages. For different definitions of automata, the recognizable languages are different.

## Variant definitions of automata自动机的变体定义

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", which we want to model using the automaton. People have studied many variations of automata. The most standard variant, which is described above, is called a deterministic finite automaton. The following are some popular variations in the definition of different components of automata.

Input

Input

• Finite input: An automaton that accepts only finite sequence of symbols. The above introductory definition only encompasses finite words.
• “有限输入”：只接受有限符号序列的自动机。上面的介绍性定义只包含有限的单词。
• Infinite input: An automaton that accepts infinite words (ω-words). Such automata are called ω-automata.
• “无限输入”：接受无限单词（ω-words）的自动机。这种自动机被称为“ω-自动机”。
• Tree word input: The input may be a tree of symbols instead of sequence of symbols. In this case after reading each symbol, the automaton reads all the successor symbols in the input tree. It is said that the automaton makes one copy 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 tree automaton.
• “树字输入”：输入可以是“符号树”，而不是符号序列。在这种情况下，在读取每个符号之后，自动机“读取”输入树中的所有后续符号。据说，自动机为每个后继者“制造一个副本”，并且每个这样的副本根据自动机的转移关系从状态开始在后继者符号之一上运行。这样的自动机称为树自动机
• Infinite tree input : The two extensions above can be combined, so the automaton reads a tree structure with (in)finite branches. Such an automaton is called an infinite tree automaton
• “无限树输入”：上面的两个扩展可以合并，因此自动机读取具有（in）有限分支的树结构。这样的自动机称为无限树自动机
States

States

• Finite states: An automaton that contains only a finite number of states. The above introductory definition describes automata with finite numbers of states.
• “有限状态”：只包含有限数量状态的自动机。上面的介绍性定义描述了状态有限的自动机。
• Stack memory: An automaton may also contain some extra memory in the form of a stack in which symbols can be pushed and popped. This kind of automaton is called a pushdown automaton
• “堆栈内存”：自动机可能还包含一些额外的内存，形式为 Stack，其中可以推送和弹出符号。一种叫“下推自动机”的机器
Transition function

Transition function

• Deterministic: 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 deterministic automaton.
• “确定性”：对于给定的当前状态和输入符号，如果自动机只能跳到一个且只有一个状态，则它是一个“确定性自动机”。
• Nondeterministic: An automaton that, after reading an input symbol, may jump into any of a number of states, as licensed by its transition relation. Notice that the term transition function is replaced by transition relation: The automaton non-deterministically decides to jump into one of the allowed choices. Such automata are called nondeterministic automata.
• “不确定性”：一种自动机，在读取输入符号后，可以跳转到许多状态中的任何一种，这是由它的转换关系授权的。注意，术语转移函数被转换关系所取代：自动机“非确定性”决定跳转到允许的选择之一。这种自动机被称为“不确定性自动机”。
• Alternation: This idea is quite similar to tree automaton, but orthogonal. The automaton may run its multiple copies on the same next read symbol. Such automata are called alternating automata. Acceptance condition must satisfy all runs of such copies to accept the input.
• “交替”：这个想法与树自动机非常相似，但是是正交的。自动机可以在“同样的”下一个读取符号上运行其“多个副本”。这种自动机称为“交替自动机”。接受条件必须满足此类“副本”的所有运行，才能接受输入。
Acceptance condition

Acceptance condition

• Acceptance of finite words: Same as described in the informal definition above.
• “有限词的接受”：与上述非正式定义相同。
• Acceptance of infinite words: an omega automaton 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.
• “接受无限词”：一个“欧米茄自动机”不能有最终状态，因为无限词永远不会终止。更确切地说，接受这个词是通过观察运行期间访问的状态的无限序列来决定的。
• Probabilistic acceptance: An automaton need not strictly accept or reject an input. It may accept the input with some probability between zero and one. For example, quantum finite automaton, geometric automaton and metric automaton have probabilistic acceptance.
• “概率接受”：自动机不需要严格地接受或拒绝输入。它可以接受介于0和1之间的概率的输入。例如，量子有限自动机，几何自动机度量自动机具有概率接受性。

Different combinations of the above variations produce many classes of automaton.

Different combinations of the above variations produce many classes of automaton.

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.

• Which class of formal languages is recognizable by some type of automata? (Recognizable languages)
• 哪一类形式语言可以被某种类型的自动机识别？（可识别语言）
• Are certain automata closed under union, intersection, or complementation of formal languages? (Closure properties)
• 在形式语言的并集、交集或互补下，某些自动机是“封闭的”吗？（闭合特性）
• How expressive is a type of automata in terms of recognizing a class of formal languages? And, their relative expressive power? (Language hierarchy)
• 就识别一类形式语言而言，自动机的表现力如何？还有，他们相对的表达能力？（语言层次）

Automata theory also studies the existence or nonexistence of any effective algorithms to solve problems similar to the following list:

• Does an automaton accept any input word? (Emptiness checking)
• 自动机接受任何输入字吗？（空检查）
• Is it possible to transform a given non-deterministic automaton into deterministic automaton without changing the recognizable language? (Determinization)
• 有没有可能在不改变可识别语言的情况下将给定的非确定性自动机转换成确定性自动机？（确定）
• For a given formal language, what is the smallest automaton that recognizes it? (Minimization)
• 对于给定的形式语言，识别它的最小自动机是什么？（最小化

## Classes of automata 自动机类

The following is an incomplete list of types of automata.

{ | class = “ wikitable”
Automaton Automaton 自动机 Recognizable language Recognizable language 可识别的语言
Nondeterministic/Deterministic Finite state machine (FSM) Nondeterministic/Deterministic Finite state machine (FSM) 不确定性/确定性有限状态机(FSM) regular languages regular languages

Deterministic pushdown automaton (DPDA) Deterministic pushdown automaton (DPDA) 确定下推自动机(DPDA) deterministic context-free languages deterministic context-free languages

Pushdown automaton (PDA) Pushdown automaton (PDA) 下推自动机 context-free languages context-free languages

Linear bounded automaton (LBA) Linear bounded automaton (LBA)

context-sensitive languages context-sensitive languages

Turing machine Turing machine 图灵机 recursively enumerable languages recursively enumerable languages

Deterministic Büchi automaton Deterministic Büchi automaton Deterministic Büchi automaton ω-limit languages ω-limit languages ω-limit languages
Nondeterministic Büchi automaton Nondeterministic Büchi automaton Nondeterministic Büchi automaton ω-regular languages ω-regular languages ω-regular languages
Rabin automaton, Streett automaton, Parity automaton, Muller automaton Rabin automaton, Streett automaton, Parity automaton, Muller automaton Rabin 自动机，Streett 自动机，奇偶自动机，Muller 自动机

### Discrete, continuous, and hybrid automata离散、连续和混合自动机

Normally automata theory describes the states of abstract machines but there are analog automata or continuous automata or hybrid discrete-continuous automata, which use analog data, continuous time, or both.

## Hierarchy in terms of powers 权力等级

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.[1]

{ | class = “ wikitable” style = “ text-align: center”
Automaton Automaton 自动机
Deterministic Finite Automaton (DFA) -- Lowest Power
Deterministic Finite Automaton (DFA) -- Lowest Power

(same power)    $\displaystyle{ || }$   (same power)

(same power)    $\displaystyle{ || }$   (same power)

(相同功率) < math > | | </math > (相同功率) < br/>

Nondeterministic Finite Automaton (NFA)

(above is weaker)    $\displaystyle{ \cap }$    (below is stronger)

(above is weaker)    $\displaystyle{ \cap }$    (below is stronger)

(上面是弱的)(下面是强的)

Deterministic Push Down Automaton (DPDA-I)

with 1 push-down store

with 1 push-down store

$\displaystyle{ \cap }$

$\displaystyle{ \cap }$

[数学]

Nondeterministic Push Down Automaton (NPDA-I)

with 1 push-down store

with 1 push-down store

$\displaystyle{ \cap }$

$\displaystyle{ \cap }$

[数学]

Linear Bounded Automaton (LBA)

$\displaystyle{ \cap }$

$\displaystyle{ \cap }$

[数学]

Deterministic Push Down Automaton (DPDA-II)

Deterministic Push Down Automaton (DPDA-II)

with 2 push-down stores

with 2 push-down stores

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Nondeterministic Push Down Automaton (NPDA-II)

Nondeterministic Push Down Automaton (NPDA-II)

with 2 push-down stores

with 2 push-down stores

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Deterministic Turing Machine (DTM)

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Nondeterministic Turing Machine (NTM)

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Probabilistic Turing Machine (PTM)

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Multitape Turing Machine (MTM)

$\displaystyle{ || }$

$\displaystyle{ || }$

[ math ] | | | | [ math ]

Multidimensional Turing Machine

## Applications 应用

Each model in automata theory plays important roles in several applied areas. Finite automata are used in text processing, compilers, and hardware design. Context-free grammar (CFGs) are used in programming languages and artificial intelligence. Originally, CFGs were used in the study of the human languages. Cellular automata are used in the field of biology, the most common example being John Conway's Game of Life. Some other examples which could be explained using automata theory in biology include mollusk and pine cones 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 Konrad Zuse, and was popularized in America by Edward Fredkin. Automata also appear in the theory of finite fields: the set of irreducible polynomials which can be written as composition of degree two polynomials is in fact a regular language.[2]

Another problem for which automata can be used is the induction of regular languages.

## Automata simulators自动机模拟器

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 can be defined in a symbolic language 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.[3]

## Connection to category theory理论分类关系

One can define several distinct categories of automata[5] following the automata classification into different types described in the previous section. The mathematical category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining the arrows between automata is a Cartesian closed category,[6][7] it has both categorical limits and colimits. An automata homomorphism maps a quintuple of an automaton Ai onto the quintuple of another automaton

Aj.[11] Automata homomorphisms can also be considered as automata transformations or as semigroup homomorphisms, when the state space, S, of the automaton is defined as a semigroup Sg. Monoids are also considered as a suitable setting for automata in monoidal categories.[12][13][14]

Aj[15] 当自动机的状态空间“S”定义为半群“S”g时，自动机同态也可以被视为“自动机变换”或半群同态。幺半群s也被认为是幺半范畴中自动机的合适设置。[16][17][18]

Categories of variable automata

## History历史

The automata theory was developed in the mid-20th century in connection with finite automata.[19]

## References参考文献

1. Yan, Song Y. (1998). An Introduction to Formal Languages and Machine Computation. Singapore: World Scientific Publishing Co. Pte. Ltd.. pp. 155–156. ISBN 9789810234225.
2. {{Citation 自动机理论中的每一个模型都在若干应用领域发挥着重要作用。有限自动机用于文本处理、编译器和硬件设计。上下文无关语法（CFGs）用于编程语言和人工智能。最初，CFGs用于人类语言的研究。细胞自动机被用于生物学领域，最常见的例子是 John Conway生命的游戏。其他一些可以用生物学中的自动机理论解释的例子包括软体动物和松果的生长和色素沉着模式。更进一步，一些科学家提出一种理论，认为整个宇宙是由某种离散自动机计算的。这个想法起源于Konrad Zuse的工作，并由Edward Fredkin在美国普及。自动机也出现在有限域理论中：可以写成二次多项式组合的不可约多项式集实际上是一种正则语言。 Each model in automata theory plays important roles in several applied areas. Finite automata are used in text processing, compilers, and hardware design. Context-free grammar (CFGs) are used in programming languages and artificial intelligence. Originally, CFGs were used in the study of the human languages. Cellular automata are used in the field of biology, the most common example being John Conway's Game of Life. Some other examples which could be explained using automata theory in biology include mollusk and pine cones 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 Konrad Zuse, and was popularized in America by Edward Fredkin. Automata also appear in the theory of finite fields: the set of irreducible polynomials which can be written as composition of degree two polynomials is in fact a regular language. 自动机理论中的每一个模型都在几个应用领域中发挥着重要作用。有限自动机用于文本处理、编译器和硬件设计。上下文无关文法被用于编程语言和人工智能。最初，cfg 被用于人类语言的研究。细胞自动机被用于生物学领域，最常见的例子是约翰 · 康威的《生命的游戏》。其他一些可以用生物学中的自动机理论来解释的例子包括软体动物和松果的生长和着色模式。更进一步，一些科学家提倡一种理论，认为整个宇宙是由某种离散的自动机计算出来的。这个想法起源于康拉德 · 祖斯的著作，并由爱德华 · 弗雷德金在美国推广。自动机也出现在有限域理论中: 不可约多项式的集合可以写成二次多项式的组合，实际上是一种规则的语言。 | last1 =Ferraguti Another problem for which automata can be used is the induction of regular languages. 另一个可以使用自动机的问题是正则语言的归纳。 | first1 =A. | last2 =Micheli | first2 =G. 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 can be defined in a symbolic language 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. 自动机模拟器是用来教授、学习和研究自动机理论的教学工具。自动机模拟器将自动机的描述作为输入，然后模拟它对任意输入字符串的工作。自动机的描述可以通过几种方式输入。自动机可以用符号语言定义，也可以用预先设计的形式输入其规范，或者通过单击和拖动鼠标绘制其转换图。著名的自动机模拟器包括图灵世界，JFLAP，增值服务，标签和 SimStudio。 | last3 =Schnyder | first3 =R. | title =Irreducible compositions of degree two polynomials over finite fields have regular structure One can define several distinct categories of automata following the automata classification into different types described in the previous section. The mathematical category of deterministic automata, sequential machines or sequential automata, and Turing machines with automata homomorphisms defining the arrows between automata is a Cartesian closed category, it has both categorical limits and colimits. An automata homomorphism maps a quintuple of an automaton Ai onto the quintuple of another automaton 根据自动机的分类，可以定义几种不同的自动机类型，这些类型在前面的章节中已有描述。确定性自动机、序列机或序列自动机的数学范畴，以及用自动机同态定义自动机之间箭头的图灵机的数学范畴是一个笛卡儿闭范畴，它既有范畴限制又有上限。自动机同态映射一个自动机 a < sub > i 的五个自动机到另一个自动机的五个自动机 | volume =69 Aj. Automata homomorphisms can also be considered as automata transformations or as semigroup homomorphisms, when the state space, S, of the automaton is defined as a semigroup Sg. Monoids are also considered as a suitable setting for automata in monoidal categories. A < sub > j .当自动机的状态空间 s 定义为半群 s < sub > g 时，自动机的同态也可以看作是自动机的变换或半群同态。幺半群也被认为是幺半群范畴中的自动机的一个合适的设置。 | issue =3 | pages =1089–1099 Categories of variable automata 可变自动机的分类 | series =The Quarterly Journal of Mathematics One could also define a variable automaton, in the sense of Norbert Wiener in his book on The Human Use of Human Beings via the endomorphisms $\displaystyle{ A_{i}\to A_{i} }$. 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 variable automaton groupoid. Therefore, in the most general case, categories of variable automata of any kind are categories of groupoids or groupoid categories. Moreover, the category of reversible automata is then a 人们也可以定义一个变量自动机，就像诺伯特 · 维纳在他的书《人有人的用处通过自同态到 a { i } </math > 。然后，我们可以证明这样的可变自动机同态构成一个数学群。在非确定自动机或其他复杂类型的自动机的情况下，后一组自同态可能成为可变的自动机群。因此，在最一般的情况下，任何类型的变量自动机的类别都是群胚类别或群胚类别的类别。进一步，可逆自动机的范畴是一个可逆自动机范畴 | publisher =Oxford University Press 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category. 2- 范畴，也是群群胚的2- 范畴的子范畴，或群群胚范畴。 | doi =10.1093/qmath/hay015 | year =2018 | arxiv =1701.06040 The automata theory was developed in the mid-20th century in connection with finite automata. 自动机理论是在20世纪中期与有限自动机相关联而发展起来的。 | s2cid =3962424 }}
3. Chakraborty, P.; Saxena, P. C.; Katti, C. P. (2011). "Fifty Years of Automata Simulation: A Review". ACM Inroads. 2 (4): 59–70. doi:10.1145/2038876.2038893. Unknown parameter |s2cid= ignored (help)
4. Chakraborty, P.; Saxena, P. C.; Katti, C. P. (2011). "Fifty Years of Automata Simulation: A Review". ACM Inroads. 2 (4): 59–70. doi:10.1145/2038876.2038893. Unknown parameter |s2cid= ignored (help)
5. Jirí Adámek and Věra Trnková. 1990. Automata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague
6. Mac Lane, Saunders (1971). Categories for the Working Mathematician. New York: Springer. ISBN 9780387900360.
7. Cartesian closed category -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔，存档日期16 November 2011.
8. Jirí Adámek and Věra Trnková. 1990. Automata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague
9. Mac Lane, Saunders (1971). Categories for the Working Mathematician. New York: Springer. ISBN 9780387900360.
10. Cartesian closed category -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔，存档日期16 November 2011.
11. The Category of Automata -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔，存档日期15 September 2011.
12. http://www.math.cornell.edu/~worthing/asl2010.pdf James Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North American Annual Meeting, 17 March 2010
13. Aguiar, M. and Mahajan, S.2010. "Monoidal Functors, Species, and Hopf Algebras".
14. Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Information and Computation 88:105–155
15. The Category of Automata -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔，存档日期15 September 2011.
16. http://www.math.cornell.edu/~worthing/asl2010.pdf James Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North American Annual Meeting, 17 March 2010
17. Aguiar, M. and Mahajan, S.2010. "Monoidal Functors, Species, and Hopf Algebras".
18. Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Information and Computation 88:105–155
19. Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. Retrieved 7 June 2020.
20. Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. Retrieved 7 June 2020.