转换表

过渡表基本上是过渡函数的表格表示。它接受两个参数(一个状态和一个符号)并返回一个状态(“下一个状态”)。
过渡表由以下内容表示:

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

文章图片
解:
【转换表】给定DFA的转换表如下:
现状输入0的下一个状态输入1的下一个状态
→q01122
q10022
*q22222
说明:
  • 在上表中,第一列指示所有当前状态。在列0和1下,显示了下一个状态。
  • 可以将过渡表的第一行读取为:当当前状态为q0时,在输入0上,下一个状态将为q1,在输入1上,下一个状态将为q2。
  • 在第二行中,当当前状态为q1时,在输入0上,下一个状态将为q0,在输入1时,下一个状态将为q2。
  • 在第三行中,当输入0上的当前状态为q2时,下一个状态将为q2,而在输入1时,下一个状态将为q2。
  • 标记为q0的箭头表示它是开始状态,标记为q2的圆圈表示它是最终状态。
范例2:
转换表

文章图片
解:
给定NFA的过渡表如下:
现状输入0的下一个状态输入1的下一个状态
→q00011
q1q1, q222
q211第3季
*q32222
说明:
  • 可以将过渡表的第一行读取为:当当前状态为q0时,在输入0上,下一个状态将为q0,在输入1上,下一个状态将为q1。
  • 在第二行中,当当前状态为q1时,在输入0时,下一个状态将为q1或q2,在输入1时,下一个状态将为q2。
  • 在第三行中,当输入0上的当前状态为q2时,下一个状态将为q1,而在输入1时,下一个状态将为q3。
  • 在第四行中,当输入0上的当前状态为q3时,下一个状态将为q2,而在输入1时,下一个状态将为q2。

    推荐阅读