首页 > 试题广场 >

不能被下面的DFA识别的字符串是（ ）

[单选题]
不能被下面的DFA识别的字符串是（   ） 

  • cbbabcb
  • cabbabcca
  • aacbc
  • bbacbc
添加回答
推荐
clear_rain头像 clear_rain
选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)
提交观点

问题信息

编译和体系结构
上传者：呼呼L
难度：
3条回答 1768浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号