转换表

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

过渡表由以下内容表示：

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

范例1：

解：

给定DFA的转换表如下：

说明：

• 在上表中，第一列指示所有当前状态。在列0和1下，显示了下一个状态。
• 可以将过渡表的第一行读取为：当当前状态为q0时，在输入0上，下一个状态将为q1，在输入1上，下一个状态将为q2。
• 在第二行中，当当前状态为q1时，在输入0上，下一个状态将为q0，在输入1时，下一个状态将为q2。
• 在第三行中，当输入0上的当前状态为q2时，下一个状态将为q2，而在输入1时，下一个状态将为q2。
• 标记为q0的箭头表示它是开始状态，标记为q2的圆圈表示它是最终状态。

范例2：

解：

给定NFA的过渡表如下：

说明：

• 可以将过渡表的第一行读取为：当当前状态为q0时，在输入0上，下一个状态将为q0，在输入1上，下一个状态将为q1。
• 在第二行中，当当前状态为q1时，在输入0时，下一个状态将为q1或q2，在输入1时，下一个状态将为q2。
• 在第三行中，当输入0上的当前状态为q2时，下一个状态将为q1，而在输入1时，下一个状态将为q3。
• 在第四行中，当输入0上的当前状态为q3时，下一个状态将为q2，而在输入1时，下一个状态将为q2。