转移表

转换表本质上是转换函数的表格表示。它接受两个参数（一个状态和一个符号）并返回一个状态（“下一个状态”）。

转换表由以下内容表示

• 列对应于输入符号。
• 行对应于状态。
• 条目对应于下一个状态。
• 起始状态用没有源的箭头表示。
• 接受状态用星号表示。

示例 1

解决方案

给定 DFA 的转换表如下

说明

• 在上表中，第一列指示所有当前状态。在第 0 列和第 1 列下，显示了下一个状态。
• 转换表的第一行可以理解为，当当前状态为 q0 时，输入 0 的下一个状态将为 q1，输入 1 的下一个状态将为 q2。
• 在第二行中，当当前状态为 q1 时，输入 0 的下一个状态将为 q0，输入 1 的下一个状态将为 q2。
• 在第三行中，当当前状态为 q2 时，输入 0 的下一个状态将为 q2，输入 1 的下一个状态将为 q2。
• 标记到 q0 的箭头表示它是一个起始状态，标记到 q2 的圆圈表示它是一个最终状态。

示例 2

解决方案

给定 NFA 的转换表如下

说明

• 转换表的第一行可以理解为，当当前状态为 q0 时，输入 0 的下一个状态将为 q0，输入 1 的下一个状态将为 q1。
• 在第二行中，当当前状态为 q1 时，输入 0 的下一个状态将为 q1 或 q2，输入 1 的下一个状态将为 q2。
• 在第三行中，当当前状态为 q2 时，输入 0 的下一个状态将为 q1，输入 1 的下一个状态将为 q3。
• 在第四行中，当当前状态为 q3 时，输入 0 的下一个状态将为 q2，输入 1 的下一个状态将为 q2。