问题 单项选择题

图2-7为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是 (14) ,图中的 (15) 是可以合并的状态。

(15)处填()。

A.0和1

B.2和3

C.1和2

D.0和3

答案

参考答案:B

解析:

[分析]: 首先将途中状态分为终态和非终态两个子集,即({0,1},{2,3)),再进行子集划分。观察第一个子集,输入b后,状态0转换为状态1,而状态1转换为状态2,因此{1}和{2}是可区别的。由于状态2,3输入字符a得到结果3,输入字符b得到相同结果2,所以子集{2, 3}是不可区别的。从而得到新的划分:({0},{1},{2,3}),即2和3是可以合并的状态。因此第二空的答案选B。重复子集划分步骤,发现新的状态无法再次划分。

删除节点3得到新的状态转换图,根据正规式和有限自动机之间的转换规则可以得到与该自动机等价的正规表达式为[a|(ba)]*bb(a*b*)*,从而第一空的答案选A。

单项选择题
单项选择题