转换图

过渡图或状态过渡图是有向图,可以按如下方式构造:

  • Q中每个状态都有一个节点,用圆圈表示。
  • 如果δ(q,a)= p,则从节点q到节点p的有向边标记为a。
  • 在开始状态下,有一个没有源的箭头。
  • 接受状态或最终状态由双圆圈表示。
过渡图中使用的一些符号:
转换图

文章图片
有关DFA的运行方式的说明:
1.在DFA中,自动机的输入可以是任何字符串。现在,将指针置于开始状态q并从左向右读取输入字符串w,然后根据转换函数δ移动指针。我们一次可以读取一个符号。如果字符串w的下一个符号是a并且指针处于状态p,则将指针移至δ(p,a)。当遇到输入字符串w的末尾时,指针将处于某个状态F。
2.如果r∈F表示字符串w被DFA接受,则表示输入字符串w被成功处理,并且自动机达到其最终状态。如果r?F,则该字符串被DFA拒绝。
范例1:
∑ = {0,1}的DFA接受以1开头的所有字符串。
解:
转换图

文章图片
可以使用过渡图来表示有限自动机。在上图中,机器最初处于启动状态q0,然后在接收到输入1时,机器将其状态更改为q1。从q0到接收0,机器将其状态更改为q2,这是死状态。机器从q1接收到输入0、1后将其状态更改为q1,这是最终状态。可能生成的输入字符串是10、11、110、101、111 … … … … .,这意味着所有字符串均以1开头。
范例2:
∑ = {0,1}的NFA接受所有以1开头的字符串。
解:
转换图

文章图片
【转换图】NFA可以使用过渡图表示。在上图中,机器最初处于启动状态q0,然后在接收到输入1时,机器将其状态更改为q1。从q1接收到输入0、1后,机器将其状态更改为q1。可能生成的输入字符串为10、11、110、101、111 … … ,这意味着所有字符串均以1开头。

    推荐阅读