单选题
某一确定有限自动机(DFA)的状态转换图如下图，与该自动机等价的正规表达式是______，图中______是可以合并的状态。
单选题
A．ab*a B．ab|ab*a C．a*b*a D．aa*|b*a
【正确答案】
A
【答案解析】可以合并的状态是指对所有可能的输入转换到相同的状态。
对应状态转移矩阵为：
可见，状态1和状态3可以合并。
状态0是初态，状态2是终态。通过a由状态0转到状态1，状态1和状态3到状态2需要通过a。因此，正规表达式应以a开头、以a结束。中间只有b。故应选A。
对应状态转移矩阵为：
a | b | |
0 | 1 | — |
1 | 2 | 3 |
3 | 2 | 3 |
2 | — | — |
状态0是初态，状态2是终态。通过a由状态0转到状态1，状态1和状态3到状态2需要通过a。因此，正规表达式应以a开头、以a结束。中间只有b。故应选A。
单选题
A．0和1 B．2和3 C．1和2 D．1和3
【正确答案】
D
【答案解析】