首页 > 试题广场 > 不能被下面的DFA识别的字符串是( )
[单选题]
不能被下面的DFA识别的字符串是(   )

  • cbbabcb
  • cabbabcca
  • aacbc
  • bbacbc
推荐
选B
【分析】

DFA全称为确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态(本题中,4和5是终态,即可作为终点)。但不同于不确定的有限自动机,DFA中不会有从同一状态出发的两条边标志有相同的符号。
简单点说就是,它是是通过event和当前的state得到下一个state,即event+state=nextstate。理解为系统中有多个节点,通过传递进入的event,来确定走哪个路由至另一个节点,而节点是有限的。



可以看出ACD的终点都是终态的节点,只有B选项不是。

编辑于 2019-05-17 14:48:35 回复(0)
选B。
DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:
  • 有一个有限状态集合和一些从一个状态通向另一个状态的边
  • 每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。
A:从节点出态0--->3--->2--->2--->4--->5--->5--->4
B:从节点出态0--->3--->1(该节点没有符号为b的出度,无法识别)--->2--->4--->5--->5--->1
C:从节点出态0--->1--->5--->5--->4--->4
D:从节点出态0--->2--->2--->4--->4--->5--->5
发表于 2019-05-16 15:52:49 回复(0)
正确答案: B

按照题目来看,所有字符串都从0开始,4或5是终点

A : 0 -> 3 -> 2 -> 2 -> 4 -> 5 -> 5 -> 4 成功来到终点
B : 0 ->  3 -> 1 -> 2 -> 2 -> 4 -> 5 -> 5 -> 5 -> 1 停在了不是终点的地方
C : 0 -> 1 -> 5 -> 5 -> 4 -> 4 成功来到终点
D : 0 -> 2 -> 2 -> 4 -> 4 -> 5 -> 5 成功来到终点

所以可以得知正确答案是B
发表于 2019-05-16 15:18:03 回复(0)