单选题
某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是
(28)
，图中
(29)
是可以合并的状态。
[*]
A、
ab*a
B、
ablab*a
C、
a*b*a
D、
aa*lb*a
【正确答案】
A
【答案解析】
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。
提交答案
关闭