fbpx
维基百科

状态转移表

十月 17, 2023

在自动机理论和时序逻辑中，状态转移表是展示有限半自动机或有限状态自动机基于当前状态和其他输入，要移动到什么状态（或在非确定有限状态自动机情况下那些状态）的表格。“状态表”本质上是其中某些输入是当前状态，而输出包含与其他输出在一起的下一个状态的真值表。

状态表是指定“状态机”的多种方式之一，其他方式包括状态图，和“特征等式”。

常见形式 编辑

一维状态表 编辑

也叫做特征表，一维状态表比二维版本更像真值表。输入通常放置在左侧，分隔于在右侧的输出。输出将表示这个机器的下一个状态。下面是有两个状态和两个组合输入的状态机的简单例子：

A B 当前状态 下一个状态 输出
0 0 S1 S2 1
0 0 S2 S1 0
0 1 S1 S2 0
0 1 S2 S2 1
1 0 S1 S1 1
1 0 S2 S1 1
1 1 S1 S1 1
1 1 S2 S2 0

S1和S2最可能表示单一位0和1，因为单一位只有两个状态。

二维状态表 编辑

状态转移图典型的是二维表。有两种安排它们的常用形式。

  • 垂直（或水平）维指示当前状态，水平（或垂直）维指示事件，表中的单元格包含在时间发生时的下一个状态（和可能的联系于这个状态转移的动作）。
状态转移表
事件
状态 		E1 E2 ... En
S1 - Ay/Sj ... -
S2 - - ... Ax/Si
... ... ... ... ...
Sm Az/Sk - ... -

（S:状态, E:事件, A:动作, -:违法转移）

  • 垂直（或水平）维指示当前状态，水平（或垂直）维指示下一个状态，单元格包含导致特定下一个状态的事件。
状态转移表
下一个
当前 		S1 S2 ... Sm
S1 Ay/Ej - ... -
S2 - - ... Ax/Ei
... ... ... ... ...
Sm - Az/Ek ... -

（S:状态, E:事件, A:动作, -:不可能转移）

例子 编辑

下面给出机器M的状态转移表和状态图。

状态转移表
输入
状态 		1 0
S1 S1 S2
S2 S2 S1
 状态图
 

表格各列枚举所有可能的给机器的输入。表格各行枚举所有可能的状态。从上面给出的状态转移表，可以轻易的看出如果机器处在S1（第一行），并且下一个输入是字符1，则机器将停留在S1。如果字符0到达了，机器将转移到可在第二列见到的S2。在图中这指示为从S1到S2的标记了0的箭头。

对于非确定有限自动机（NFA），一个新输入可以导致机器进入多于一个状态，因此是非确定性的。这在状态转移表中指示为一对花括号包围的所有目标状态的集合。下面给出一个例子。

NFA的状态转移表
输入
状态 		1 0 ε
S1 S1 { S2, S3 } Φ
S2 S2 S1 Φ
S3 S2 S1 S1

这里的非确定机器处在状态S1读入一个输入0将导致它同时处在两种状态，即状态S2和S3。最后的列定义特殊字符ε的合法转移。这个特殊字符允许NFA在没有输入的时候移动到不同状态。在状态S3，NFA可以移动到S1而不消耗任何输入字符。上述两种情况使描述的有限自动机是非确定性的。

变换成状态图 编辑

有可能从表格绘制状态图。下面给出步骤：

  1. 绘制圆圈表示给出状态。
  2. 对于每个状态，检索对应的行绘制到目的状态的箭头。如果自动机是NFA则对一个输入字母可能有多个箭头。
  3. 指定一个状态为开始状态。开始状态在自动机的形式定义中给出。
  4. 指定一个或多个状态为接受状态。它也在自动机的形式定义中给出。

引用 编辑

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X

十月 17, 2023
状态转移表, 在自动机理论和时序逻辑中, 是展示有限半自动机或有限状态自动机基于当前状态和其他输入, 要移动到什么状态, 或在非确定有限状态自动机情况下那些状态, 的表格, 状态表, 本质上是其中某些输入是当前状态, 而输出包含与其他输出在一起的下一个状态的真值表, 状态表是指定, 状态机, 的多种方式之一, 其他方式包括状态图, 特征等式, 目录, 常见形式, 一维状态表, 二维状态表, 例子, 变换成状态图, 引用常见形式, 编辑一维状态表, 编辑, 也叫做特征表, 一维状态表比二维版本更像真值表, 输入通常放. 在自动机理论和时序逻辑中 状态转移表是展示有限半自动机或有限状态自动机基于当前状态和其他输入 要移动到什么状态 或在非确定有限状态自动机情况下那些状态 的表格 状态表 本质上是其中某些输入是当前状态 而输出包含与其他输出在一起的下一个状态的真值表 状态表是指定 状态机 的多种方式之一 其他方式包括状态图 和 特征等式 目录 1 常见形式 1 1 一维状态表 1 2 二维状态表 2 例子 3 变换成状态图 4 引用常见形式 编辑一维状态表 编辑 也叫做特征表 一维状态表比二维版本更像真值表 输入通常放置在左侧 分隔于在右侧的输出 输出将表示这个机器的下一个状态 下面是有两个状态和两个组合输入的状态机的简单例子 A B 当前状态 下一个状态 输出0 0 S1 S2 10 0 S2 S1 00 1 S1 S2 00 1 S2 S2 11 0 S1 S1 11 0 S2 S1 11 1 S1 S1 11 1 S2 S2 0S1和S2最可能表示单一位0和1 因为单一位只有两个状态 二维状态表 编辑 状态转移图典型的是二维表 有两种安排它们的常用形式 垂直 或水平 维指示当前状态 水平 或垂直 维指示事件 表中的单元格包含在时间发生时的下一个状态 和可能的联系于这个状态转移的动作 状态转移表 事件状态 E1 E2 EnS1 Ay Sj S2 Ax Si Sm Az Sk S 状态 E 事件 A 动作 违法转移 垂直 或水平 维指示当前状态 水平 或垂直 维指示下一个状态 单元格包含导致特定下一个状态的事件 状态转移表 下一个当前 S1 S2 SmS1 Ay Ej S2 Ax Ei Sm Az Ek S 状态 E 事件 A 动作 不可能转移 例子 编辑下面给出机器M的状态转移表和状态图 状态转移表 输入状态 1 0S1 S1 S2S2 S2 S1 状态图 nbsp 表格各列枚举所有可能的给机器的输入 表格各行枚举所有可能的状态 从上面给出的状态转移表 可以轻易的看出如果机器处在S1 第一行 并且下一个输入是字符1 则机器将停留在S1 如果字符0到达了 机器将转移到可在第二列见到的S2 在图中这指示为从S1到S2的标记了0的箭头 对于非确定有限自动机 NFA 一个新输入可以导致机器进入多于一个状态 因此是非确定性的 这在状态转移表中指示为一对花括号包围的所有目标状态的集合 下面给出一个例子 NFA的状态转移表 输入状态 1 0 eS1 S1 S2 S3 FS2 S2 S1 FS3 S2 S1 S1这里的非确定机器处在状态S1读入一个输入0将导致它同时处在两种状态 即状态S2和S3 最后的列定义特殊字符e的合法转移 这个特殊字符允许NFA在没有输入的时候移动到不同状态 在状态S3 NFA可以移动到S1而不消耗任何输入字符 上述两种情况使描述的有限自动机是非确定性的 变换成状态图 编辑有可能从表格绘制状态图 下面给出步骤 绘制圆圈表示给出状态 对于每个状态 检索对应的行绘制到目的状态的箭头 如果自动机是NFA则对一个输入字母可能有多个箭头 指定一个状态为开始状态 开始状态在自动机的形式定义中给出 指定一个或多个状态为接受状态 它也在自动机的形式定义中给出 引用 编辑Michael Sipser Introduction to the Theory of Computation PWS Publishing Co Boston 1997 ISBN 0 534 94728 X 取自 https zh wikipedia org w index php title 状态转移表 amp oldid 43052511, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。