更改

[[File:DFAexample.svg|thumb|300px|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 ''0''s. 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 machine]]s and [[automaton|automata]], as well as the [[computational problem]]s 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".

[[File:DFAexample.svg|thumb|300px|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 ''0''s. 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.|链接=Special:FilePath/DFAexample.svg]]'''Automata theory''' is the study of [[abstract machine]]s and [[automaton|automata]], as well as the [[computational problem]]s 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".

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

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

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

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

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.

对这类<font color="#ff8000"> 自动机Automata</font>的数学性质的研究是自动机理论。图片是一个可视化的<font color="#ff8000"> 自动机</font>，它可以识别包含偶数个0的字符串。自动机从状态 S1开始，读取符号0后转换到不接受状态 S2。读取另一个0会导致自动机转换回接受状态 S1。在这两种状态下，符号1通过转换到当前状态而被忽略。自动机理论是研究抽象的机器和自动机，以及利用它们可以解决的计算问题。这是一个理论计算机科学的理论。单词 automata (automaton 的复数形式)来源于希腊词 α something τματα，意思是“自我创造”。

对这类<font color="#ff8000"> 自动机Automata</font>的数学性质的研究是自动机理论。图片是一个被可视化的<font color="#ff8000"> 自动机</font>，它可以识别包含偶数个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 [[State (computer science)|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 system|transition function]], which takes the current state and the recent symbol as its inputs.

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

右边的图表显示了一个有限状态机，它属于一种著名的自动机类型。这个<font color="#ff8000"> 自动机</font>由状态(在图中用圆圈表示)和转换(用箭头表示)组成。当<font color="#ff8000"> 自动机</font>看到一个输入符号时，它根据其转换函数将当前状态和最近的符号作为输入，转换(或跳转)到另一个状态。

右边的图表显示了一个有限状态机，它属于一种著名的自动机类型。这个<font color="#ff8000"> 自动机</font>由状态(在图中用圆圈表示)和转换(用箭头表示)组成。当<font color="#ff8000"> 自动机</font>看到一个输入符号时，它根据其转换函数将当前状态和最近的符号作为输入，转换(或跳转)到另一个状态。

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

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

==Automata自动机==

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

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

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.

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 的地方时应该做什么一样)。当机器接收到一个新的输入时，它会查看状态，并根据接收到该状态的输入时应该做什么的信息来选择一个新点。当没有更多的输入时，自动机停止，并且当它完成时所处的空间决定了自动机是否接受或拒绝特定的输入集。

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

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 ''[[Symbol (formal)|symbols]]'' or ''letters'', which is called an ''[[alphabet (computer science)|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 ''[[formal language|language]] recognized by the automaton''.

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 ''[[Symbol (formal)|symbols]]'' or ''letters'', which is called an ''[[alphabet (computer science)|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 ''[[formal language|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|date=May 2012}}, automata theory plays a crucial role in [[computational theory]].

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|date=May 2012}}, automata theory plays a crucial role in [[computational theory]].

简而言之，自动机是一个数学对象，它接受一个单词作为输入，并决定是否接受它。由于所有的计算问题都可以简化为输入的接受/拒绝问题(所有问题实例都可以用有限长度的符号表示) ,自动机理论在计算理论中起着至关重要的作用。

简而言之，自动机是一个数学对象，它接受一个单词作为输入，并决定是否接受它。由于所有的计算问题都可以简化为输入的接受/拒绝问题(所有问题实例都可以用有限长度的符号表示) ,自动机理论在计算理论中起着至关重要的作用。

:A deterministic finite '''automaton''' is represented formally by a [[N-tuple|5-tuple]] {{not a typo|'''<Q, [[Sigma|Σ]], [[Delta (letter)|δ]],q₀,F>'''}}, where:

:A deterministic finite '''automaton''' is represented formally by a [[N-tuple|5-tuple]] {{not a typo|'''<Q, [[Sigma|Σ]], [[Delta (letter)|δ]],q₀,F>'''}}, where:

确定性有限状态自动机的正式定义包含五项，其中:

 

确定性有限状态自动机的正式表示是一个5元组，其中:

:* Q is a finite set of ''states''.

:* Q is a finite set of ''states''.

* Q 是状态的有限集合。

* Q 是状态的有限集合。

:* [[Sigma|Σ]] is a finite set of ''[[symbol]]s'', called the ''[[alphabet (computer science)|alphabet]]'' of the automaton.

:* [[Sigma|Σ]] is a finite set of ''[[symbol]]s'', called the ''[[alphabet (computer science)|alphabet]]'' of the automaton.

*  [[Sigma|Σ]]是一个有限的符号集，称为自动机字母表。

*  [[Sigma|Σ]]是一个有限的符号集，称为自动机字母表。

:* [[Delta (letter)|δ]] is the '''transition function''', that is, δ:&nbsp;Q&nbsp;×&nbsp;Σ&nbsp;→&nbsp;Q.

:* [[Delta (letter)|δ]] is the '''transition function''', that is, δ:&nbsp;Q&nbsp;×&nbsp;Σ&nbsp;→&nbsp;Q.

* δ 是跃迁函数，即 δ: 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₀ is the ''start state'', that is, the state of the automaton before any input has been processed, where q₀∈ Q.

* q₀ 是起始状态，即自动机在任意输入被处理之前的状态，其中 q₀∈ Q。

* q₀ 是起始状态，即自动机在任意输入被处理之前的状态，其中 q₀∈ Q。

:* F is a set of states of Q (i.e. F⊆Q) called '''accept states'''.

:* F is a set of states of Q (i.e. F⊆Q) called '''accept states'''.

* F 是 Q (i.e. F⊆Q) 的一组状态称为“接受状态”。

* F 是 Q (i.e. F⊆Q) 的一组状态称为“接受状态”。

:An automaton reads a finite [[Word (mathematics)|string]] of symbols a₁,a₂,...., a_n , where a_i&nbsp;∈&nbsp;Σ, which is called an ''input word''. The set of all words is denoted by Σ*.

:An automaton reads a finite [[Word (mathematics)|string]] of symbols a₁,a₂,...., a_n , where a_i&nbsp;∈&nbsp;Σ, which is called an ''input word''. The set of all words is denoted by Σ*.

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

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

:A sequence of states q₀,q₁,q₂,...., q_n, where q_i&nbsp;∈&nbsp;Q such that q₀ is the start state and q_i&nbsp;=&nbsp;δ(q_i-1,a_i) for 0&nbsp;&lt;&nbsp;i&nbsp;≤&nbsp;n, is a ''run'' of the automaton on an input word w = a₁,a₂,...., a_n&nbsp;∈&nbsp;Σ*. 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&nbsp;=&nbsp;δ(q_i-1,a_i). q_n is said to be the ''final state'' of the run.

:A sequence of states q₀,q₁,q₂,...., q_n, where q_i&nbsp;∈&nbsp;Q such that q₀ is the start state and q_i&nbsp;=&nbsp;δ(q_i-1,a_i) for 0&nbsp;&lt;&nbsp;i&nbsp;≤&nbsp;n, is a ''run'' of the automaton on an input word w = a₁,a₂,...., a_n&nbsp;∈&nbsp;Σ*. 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&nbsp;=&nbsp;δ(q_i-1,a_i). q_n is said to be the ''final state'' of the run.

A sequence of states q₀,q₁,q₂,...., q_n, where q_i&nbsp;∈&nbsp;Q such that q₀ is the start state and q_i&nbsp;=&nbsp;δ(q_i-1,a_i) for 0&nbsp;&lt;&nbsp;i&nbsp;≤&nbsp;n, is a run of the automaton on an input word w = a₁,a₂,...., a_n&nbsp;∈&nbsp;Σ*. 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&nbsp;=&nbsp;δ(q_i-1,a_i). q_n is said to be the final state of the run.

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

:A word w&nbsp;∈&nbsp;Σ* is accepted by the automaton if q_n&nbsp;∈&nbsp;F.

:A word w&nbsp;∈&nbsp;Σ* is accepted by the automaton if q_n&nbsp;∈&nbsp;F.

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

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

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

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

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

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

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

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

可识别的语言是由某些自动机识别的一组语言。对于上述自动机的定义，可识别的语言是正则语言。对于不同的自动机定义，可识别的语言是不同的。

可识别的语言是由某些自动机识别的一组语言。对于上述自动机的定义，可识别的语言是正则语言。对于不同的自动机定义，可识别的语言是不同的。

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.

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.

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.

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.

Automata theory also studies the existence or nonexistence of any [[effective method|effective algorithm]]s to solve problems similar to the following list:

Automata theory also studies the existence or nonexistence of any [[effective method|effective algorithm]]s to solve problems similar to the following list:

自动机理论还研究是否存在任何有效的算法来解决类似以下列表的问题:

自动机理论还研究是否存在任何有效的算法来解决类似以下列表的问题:

== Classes of automata 自动机类==

== Classes of automata 自动机类==

The following is an incomplete list of types of automata.

The following is an incomplete list of types of automata.

| Rabin 自动机，Streett 自动机，奇偶自动机，Muller 自动机

| Rabin 自动机，Streett 自动机，奇偶自动机，Muller 自动机

|}

|}

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

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

通常来讲自动机理论描述抽象机器的状态，但存在有类比自动机、连续自动机或混合离散-连续自动机，它们使用模拟数据、连续时间或两者兼用。

 

通常自动机理论描述抽象机器的状态，但存在有类比自动机、连续自动机或混合离散-连续自动机，它们使用模拟数据、连续时间或两者兼用。

== Hierarchy in terms of powers 权力等级==

== 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.<ref name="Aaniya B">{{cite book|last=Yan|first=Song Y.|title=An Introduction to Formal Languages and Machine Computation|year=1998|publisher=World Scientific Publishing Co. Pte. Ltd.|location=Singapore|pages=155–156|url=https://books.google.com/books?id=ySOwQgAACAAJ|isbn=9789810234225}}</ref>  

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.<ref name="Aaniya B">{{cite book|last=Yan|first=Song Y.|title=An Introduction to Formal Languages and Machine Computation|year=1998|publisher=World Scientific Publishing Co. Pte. Ltd.|location=Singapore|pages=155–156|url=https://books.google.com/books?id=ySOwQgAACAAJ|isbn=9789810234225}}</ref>

 

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

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

多维图灵机

多维图灵机

|}

|}

== Applications 应用==

== 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 Horton Conway|John Conway]]'s [[Conway's Game of Life|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.<ref>{{Citation

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 Horton Conway|John Conway]]'s [[Conway's Game of Life|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.<ref><nowiki>{{Citation

自动机理论中的每一个模型都在若干应用领域发挥着重要作用。[[有限自动机]]用于文本处理、编译器和硬件设计。[[上下文无关语法]]（CFGs）用于编程语言和人工智能。最初，CFGs用于人类语言的研究。[[细胞自动机]]被用于生物学领域，最常见的例子是[[John Horton Conway | John Conway]]的[[生命的游戏]]。其他一些可以用生物学中的自动机理论解释的例子包括软体动物和松果的生长和色素沉着模式。更进一步，一些科学家提出一种理论，认为整个宇宙是由某种离散自动机计算的。这个想法起源于[[Konrad Zuse]]的工作，并由[[Edward Fredkin]]在美国普及。自动机也出现在有限域理论中：可以写成二次多项式组合的不可约多项式集实际上是一种正则语言。

自动机理论中的每一个模型都在若干应用领域发挥着重要作用。</nowiki>[[有限自动机]]用于文本处理、编译器和硬件设计。[[上下文无关语法]]（CFGs）用于编程语言和人工智能。最初，CFGs用于人类语言的研究。[[细胞自动机]]被用于生物学领域，最常见的例子是[[John Horton Conway | 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.

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 被用于人类语言的研究。细胞自动机被用于生物学领域，最常见的例子是约翰 · 康威的《生命的游戏》。其他一些可以用生物学中的自动机理论来解释的例子包括软体动物和松果的生长和着色模式。更进一步，一些科学家提倡一种理论，认为整个宇宙是由某种离散的自动机计算出来的。这个想法起源于康拉德 · 祖斯的著作，并由爱德华 · 弗雷德金在美国推广。自动机也出现在有限域理论中: 不可约多项式的集合可以写成二次多项式的组合，实际上是一种规则的语言。

自动机理论中的每一个模型都在几个应用领域中发挥着重要作用。有限自动机用于文本处理、编译器和硬件设计。上下文无关文法被用于编程语言和人工智能。最初，cfg 被用于人类语言的研究。细胞自动机被用于生物学领域，最常见的例子是约翰 · 康威的《生命的游戏》。其他一些可以用生物学中的自动机理论来解释的例子包括软体动物和松果的生长和着色模式。更进一步，一些科学家提倡一种理论，认为整个宇宙是由某种离散的自动机计算出来的。这个想法起源于康拉德 · 祖斯的著作，并由爱德华 · 弗雷德金在美国推广。自动机也出现在有限域理论中: 不可约多项式的集合可以写成二次多项式的组合，实际上是一种规则的语言。

   | last1 = Ferraguti

   | last1 =Ferraguti

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

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

另一个可以使用自动机的问题是正则语言的归纳。

另一个可以使用自动机的问题是正则语言的归纳。

   | first1 = A.

   | first1 =A.

   | last2 = Micheli

   | last2 =Micheli

   | first2 = G.

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

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。

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

   | last3 = Schnyder

   | last3 =Schnyder

   | first3 = R.

   | first3 =R.

   | title = Irreducible compositions of degree two polynomials over finite fields have regular structure

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

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  

根据自动机的分类，可以定义几种不同的自动机类型，这些类型在前面的章节中已有描述。确定性自动机、序列机或序列自动机的数学范畴，以及用自动机同态定义自动机之间箭头的图灵机的数学范畴是一个笛卡儿闭范畴，它既有范畴限制又有上限。自动机同态映射一个自动机 a < sub > i </sub > 的五个自动机到另一个自动机的五个自动机

根据自动机的分类，可以定义几种不同的自动机类型，这些类型在前面的章节中已有描述。确定性自动机、序列机或序列自动机的数学范畴，以及用自动机同态定义自动机之间箭头的图灵机的数学范畴是一个笛卡儿闭范畴，它既有范畴限制又有上限。自动机同态映射一个自动机 a < sub > i 的五个自动机到另一个自动机的五个自动机

   | volume = 69

   | volume =69

  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. 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 < sub > j </sub > .当自动机的状态空间 s 定义为半群 s < sub > g </sub > 时，自动机的同态也可以看作是自动机的变换或半群同态。幺半群也被认为是幺半群范畴中的自动机的一个合适的设置。

A < sub > j .当自动机的状态空间 s 定义为半群 s < sub > g 时，自动机的同态也可以看作是自动机的变换或半群同态。幺半群也被认为是幺半群范畴中的自动机的一个合适的设置。

   | issue = 3

   | issue =3

   | pages = 1089–1099

   | pages =1089–1099

Categories of variable automata

Categories of variable automata

可变自动机的分类

可变自动机的分类

   | series = The Quarterly Journal of Mathematics

   | 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 <math>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  

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

人们也可以定义一个变量自动机，就像诺伯特 · 维纳在他的书《人有人的用处通过自同态到 a { i } </math > 。然后，我们可以证明这样的可变自动机同态构成一个数学群。在非确定自动机或其他复杂类型的自动机的情况下，后一组自同态可能成为可变的自动机群。因此，在最一般的情况下，任何类型的变量自动机的类别都是群胚类别或群胚类别的类别。进一步，可逆自动机的范畴是一个可逆自动机范畴

人们也可以定义一个变量自动机，就像诺伯特 · 维纳在他的书《人有人的用处通过自同态到 a { i } <nowiki></math ></nowiki> 。然后，我们可以证明这样的可变自动机同态构成一个数学群。在非确定自动机或其他复杂类型的自动机的情况下，后一组自同态可能成为可变的自动机群。因此，在最一般的情况下，任何类型的变量自动机的类别都是群胚类别或群胚类别的类别。进一步，可逆自动机的范畴是一个可逆自动机范畴

  | publisher = Oxford University Press

<nowiki> </nowiki> <nowiki>|</nowiki> publisher =Oxford University Press

2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

2- 范畴，也是群群胚的2- 范畴的子范畴，或群群胚范畴。

2- 范畴，也是群群胚的2- 范畴的子范畴，或群群胚范畴。

  | doi = 10.1093/qmath/hay015

<nowiki> </nowiki> <nowiki>|</nowiki> doi =10.1093/qmath/hay015

  | year = 2018

<nowiki> </nowiki> <nowiki>|</nowiki> year =2018

  | arxiv = 1701.06040

<nowiki> </nowiki> <nowiki>|</nowiki> arxiv =1701.06040

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

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

自动机理论是在20世纪中期与有限自动机相关联而发展起来的。

自动机理论是在20世纪中期与有限自动机相关联而发展起来的。

  | s2cid = 3962424

<nowiki> </nowiki> <nowiki>|</nowiki> s2cid =3962424

}}</ref>

<nowiki> </nowiki>}}</ref>

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

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