如图3－1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是

Question

如图3-1所示为一确定有限自动机(DFA)的状态转换图，与该自动机等价的正规表达式是(1)，图中的(2)是可以合并的状态。

A．(a|b)* bb(a*b*)*

B．(a|b)*bba*|b*

C．(a*b*)bb(a|b)*

D．(a*|b*)*bb(a*|b*)

Answer 1

正确答案：A
解析：在状态转换图中，每一个结点代表一个状态，其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程，一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
  首先介绍2个概念：最小状态DFA和等价状态。
  最小状态DFA必须满足以下2个条件。
  (1)没有多余状态(死状态)：多余状态从该自动机的开始状态出发，任何输入串都不能到达的那个状态。
  (2)没有2个状态是互相等价(不可区别)。
  2个状态s和t如果同时满足下列2个条件，就称s和t是等价的。
  (1)一致性：同是终态或同是非终态。
  (2)蔓延性：从s出发读人某个a和从t出发读入某个a到达的状态等价。
  本题的简化过程如下：
  首先，将图中状态分为终态和非终态2个子集即({0,1},{2,3})，再进行子集划分，观察第一个子集{0,1}，输入b后，状态0转换为状态1，而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
  由于状态2,3输入字符a得到相同的结果3，输入字符b得到相同结果2，所以子集 {2,3}是不可区别的。从而得到新的划分：({0}，{1}，{2，3})，因此，(2)空的正确答案为B。
  重复子集划分步骤，发现新的状态无法再次划分。
  所以，本题中2，3状态可以消除3状态，得到新的状态转换图如图3-2所示。
 
  由图3-2可知终态2可以转换为正规表达式(a|b)*，同时必须输入连续2个b字符，才能完成0状态到终态2的转换，所以结果正规表达式必为形如“...bb(a|b)*”的字符串。又因为0和1之间由b和a轮回输入，可以表示为(ba)*，同时，状态0上输入a又回到自身，可以表示为a*。因此，(1)空的正确答案应该为(a*b*)*bb(a|b)*，根据正规式之间的代数性质，(a*b*)*bb(a|b)*与(a|b)*bb(a*b*)*等价。