自动机理论

此词条暂由水流心不竞初译，翻译字数共，Inch正在审校，带来阅读不便，请见谅。

文件:DFAexample.svg

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".

对这种自动机的数学性质的研究是自动机理论。此图是自动机的可视化，它识别包含偶数个“0”的字符串。自动机从状态“S1”开始，在读取符号“0”时转换到不接受状态“S2”。读取另一个“0”会导致自动机转换回接受状态“S1”。在这两种状态下，符号“1”通过转换回当前状态而被忽略。

“自动机理论”是对抽象机器和自动机以及使用它们可以解决的计算性问题的研究。它是[[理论计算机科学]中的一个理论。“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.

对这类 自动机Automata的数学性质的研究是自动机理论。图片是一个被可视化的 自动机，它可以识别包含偶数个0的字符串。自动机从状态 S1开始，读取符号0后转换到不接受状态 S2。读取另一个0会导致自动机转换回接受状态 S1。在这两种状态下，符号1通过转换到当前状态而被忽略。

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.

自动机理论与形式语言理论密切相关。自动机是形式语言的有限表示，语言这里可以是一个无限集合。 自动机通常按照它们能够识别的形式语言类别进行分类，典型的例子是描述各种语言和各种形式化逻辑之间关系的 乔姆斯基谱系Chomsky hierarchy。

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.

自动机是一个由状态构成的结构，它被设计用来决定输入是否应该被接受或被拒绝。它看起来很像一个基本的棋盘游戏，棋盘上的每个空格代表一种状态。每个状态都有关于当机器接收到输入时应该做什么的信息(同样，就像在一个流行的棋盘游戏中，当你落在 Go To Jail 的地方时应该做什么一样)。当机器接收到一个新的输入时，它会查看状态，并根据接收到该状态的输入时应该做什么的信息来选择一个新点。当没有更多的输入时，自动机停止，并且当它完成时所处的空间决定了自动机是否接受或拒绝特定的输入集。

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), 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 a finite set of symbols, called the alphabet of the automaton.

• Σ是一个有限的符号集，称为自动机字母表。

• δ is the transition function, that is, δ: Q × Σ → Q.

• δ 是跃迁函数，即 δ: q × σ → q。

• q₀ is the start state, that is, the state of the automaton before any input has been processed, where q₀∈ Q.

• q₀ 是起始状态，即自动机在任意输入被处理之前的状态，其中 q₀∈ 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 a₁,a₂,...., a_n , where a_i ∈ Σ, which is called an input word. The set of all words is denoted by Σ*.

一个自动机读取一个有限的符号串 a₁,a₂,...., a_n , 其中 a_i ∈ Σ，称为输入字。所有单词的集合用Σ* 表示。

Run

Run

运行

A sequence of states q₀,q₁,q₂,...., q_n, where q_i ∈ Q such that q₀ is the start state and q_i = δ(q_i-1,a_i) for 0 < i ≤ n, is a run of the automaton on an input word w = a₁,a₂,...., a_n ∈ Σ*. In other words, at first the automaton is at the start state q₀, and then the automaton reads symbols of the input word in sequence. When the automaton reads symbol a_i it jumps to state q_i = δ(q_i-1,a_i). q_n is said to be the final state of the run.

状态序列 q₀,q₁,q₂,...., q_n, 其中 q_i ∈ Q 使得 q₀为起始状态，并且q_i = δ(q_i-1,a_i)对于0 < i ≤ n，是自动机在输入字 w = a₁,a₂,...., a_n ∈ Σ*上的运行结果,....本文研究了一类非线性规划问题，即 a < sub > n ∈ σ * 。换句话说，首先自动机处于启动状态 q₀ ，然后自动机按顺序读取输入词的符号。当自动机读取符号 a_i 时，它跳转到状态 q_i = δ(q_i-1,a_i)。q_n 被认为是运行的最终状态。

Accepting word

Accepting word

接受词

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

如果 q_n ∈ F，则 w ∈ Σ* 为自动机所接受。

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.

自动机可以识别正式语言。自动机所识别的 L ⊆ Σ* 语言是自动机所接受的所有单词的集合。

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.

• “有限状态”：只包含有限数量状态的自动机。上面的介绍性定义描述了状态有限的自动机。

• Infinite states: An automaton that may not have a finite number of states, or even a countable number of states. For example, the quantum finite automaton or topological automaton has uncountable infinity 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.

下面是按照不同类型的虚拟机的权力划分的不完全层次结构。层次结构反映了机器能够接受的语言的嵌套类别。

{ | class = “ wikitable” style = “ text-align: center”

Automaton	Automaton	自动机
Deterministic Finite Automaton (DFA) -- Lowest Power	Deterministic Finite Automaton (DFA) -- Lowest Power	确定有限状态自动机(DFA) -- 最低功耗 < br/> (same power)    [math]\displaystyle{ || }[/math]   (same power) (same power)    [math]\displaystyle{ || }[/math]   (same power) (相同功率) < math > | | </math > (相同功率) < br/> Nondeterministic Finite Automaton (NFA) Nondeterministic Finite Automaton (NFA) 非确定有限状态自动机 < br/> (above is weaker)    [math]\displaystyle{ \cap }[/math]    (below is stronger) (above is weaker)    [math]\displaystyle{ \cap }[/math]    (below is stronger) (上面是弱的)(下面是强的) Deterministic Push Down Automaton (DPDA-I) Deterministic Push Down Automaton (DPDA-I) 确定性下推自动机(DPDA-I) < br/> with 1 push-down store with 1 push-down store 只有一个下推式商店 [math]\displaystyle{ \cap }[/math] [math]\displaystyle{ \cap }[/math] [数学] Nondeterministic Push Down Automaton (NPDA-I) Nondeterministic Push Down Automaton (NPDA-I) 不确定下推自动机(NPDA-I) < br/> with 1 push-down store with 1 push-down store 只有一个下推式商店 [math]\displaystyle{ \cap }[/math] [math]\displaystyle{ \cap }[/math] [数学] Linear Bounded Automaton (LBA) Linear Bounded Automaton (LBA) 线性有界自动机 [math]\displaystyle{ \cap }[/math] [math]\displaystyle{ \cap }[/math] [数学] Deterministic Push Down Automaton (DPDA-II) Deterministic Push Down Automaton (DPDA-II) 确定性下推自动机(DPDA-II) < br/> with 2 push-down stores with 2 push-down stores 有两个下拉式商店 [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Nondeterministic Push Down Automaton (NPDA-II) Nondeterministic Push Down Automaton (NPDA-II) 不确定下推自动机(NPDA-II) < br/> with 2 push-down stores with 2 push-down stores 有两个下拉式商店 [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Deterministic Turing Machine (DTM) Deterministic Turing Machine (DTM) 确定性图灵机(DTM) < br/> [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Nondeterministic Turing Machine (NTM) Nondeterministic Turing Machine (NTM) 不确定图灵机(NTM) < br/> [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Probabilistic Turing Machine (PTM) Probabilistic Turing Machine (PTM) 机率图灵机 [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Multitape Turing Machine (MTM) Multitape Turing Machine (MTM) 多带图灵机 [math]\displaystyle{ || }[/math] [math]\displaystyle{ || }[/math] [ math ] | | | | [ math ] Multidimensional Turing Machine 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.

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.

自动机模拟器是用来教授、学习和研究自动机理论的教学工具。自动机模拟器将自动机的描述作为输入，然后模拟其对任意输入字符串的工作。自动机的描述可以用几种方式输入。自动机可以用符号语言来定义，或者以预先设计的形式输入其规范，或者通过单击和拖动鼠标绘制其转换图。著名的自动机模拟器包括图灵世界、JFLAP、VAS、TAGS和SimStudio。

Connection to category theory理论分类关系

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 A_i onto the quintuple of another automaton

遵循上一节中描述的自动机分类法我们可以定义几个不同范畴的自动机。确定性自动机的数学范畴，sequential machines或“序列自动机”，以及具有定义自动机之间箭头的自动机同态的图灵机是笛卡尔闭范畴，它既有分类界限，又有公共限制。自动机同态映射一个五元组的自动机A_i到另一个自动机的五元组上。

A_j. 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 S_g. Monoids are also considered as a suitable setting for automata in monoidal categories.

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

Categories of variable automata

可变自动机的分类 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 [math]\displaystyle{ A_{i}\to A_{i} }[/math]. 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 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

人们也可以定义一个“变量自动机”，在他关于“人类的使用”的书中，Norbert Wiener”“通过”了自同态[math]\displaystyle{ A_{i}\to A_{i} }[/math]。然后，我们可以证明这样的变量自动机同态形成了一个数学群。然而，在后一类自动机中，[或]一类复杂的自动机可能会成为一个复杂的自形集。因此，在最一般的情况下，任何类型的变量自动机的类别都是群的范畴或类群范畴。而且，可逆自动机的范畴是二元的2-category，并且也是群的2元同胚2-category或群的子类别。

History历史

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

自动机理论是在20世纪中叶与有限自动机相结合而发展起来的。

See also请参阅

• Boolean differential calculus

Further reading延伸阅读

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Pearson Education. ISBN 978-0-201-44124-6. 

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6.  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.

• Elaine Rich (2008). Automata, Computability and Complexity: Theory and Applications. Pearson. ISBN 978-0-13-228806-4. 

• Salomaa, Arto (1985). Computation and automata. Encyclopedia of Mathematics and Its Applications. 25. Cambridge University Press. ISBN 978-0-521-30245-6. Zbl 0565.68046. https://archive.org/details/computationautom0000salo. 

• Anderson, James A. (2006). Automata theory with modern applications. With contributions by Tom Head. Cambridge: Cambridge University Press. ISBN 978-0-521-61324-8. Zbl 1127.68049. 

• Conway, J.H. (1971). Regular algebra and finite machines. Chapman and Hall Mathematics Series. London: Chapman & Hall. Zbl 0231.94041. 

• John M. Howie (1991) Automata and Languages, Clarendon Press
  模板:Mr
  • Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177. 

  
  

  This page was moved from wikipedia:en:Automata theory. Its edit history can be viewed at 自动机理论/edithistory