问题
单项选择题
某一确定有限自动机(DFA)的状态转换图如下图,与该自动机等价的正规表达式是 (28) ,图中 (29) 是可以合并的状态。
[*]
A.0和1
B.2和3
C.1和2
D.1和3
答案
参考答案:D
解析:可以合并的状态是指对所有可能的输入转换到相同的状态。
对应状态转移矩阵为:
[*]
可见,状态1和状态3可以合并。
状态0是初态,状态2是终态。通过a由状态0转到状态1,状态1和状态3到状态2需要通过a。是故,正规表达式应以a开头、以a结束。中间只有b。故应选A。