为下列正规式构造最简的DFA： （1)（a｜b)*a（a｜b) （2)（a｜b)*a（a｜b)（a｜b) （3)（a｜b)*a（
,状态
已帮助 人
为下列正规式构造最简的DFA： (1)(a｜b)*a(a｜b) (2)(a｜b)*a(a｜b)(a｜b) (3)(a｜b)*a(a｜b)(a｜b)(a｜b) 并估算(a｜b)*a(a｜b)(a｜b)…(a｜b)(共有n－1个(a｜b))对应的任何一个DFA至少有多少个状态。
请帮忙给出正确答案和分析，谢谢！
-
参考答案：(1)正规式对应的NFA如图2—19所示。 确定化求解的状态表如表2—17和表2—18所示。最小化的DFA如表2—19所示。 (2)正规式对应的NFA如图2—20所示。 确定化求解的状态表如表2—20和表2—21所示。最小化的DFA如表2—22所示。 (3)正规式对应的NFA如图2—21所示。 确定化求解的状态表如表2—23和表2—24所示。最小化的DFA如表2—25所示。 (a｜b)a(a｜b)(a｜b)…(a｜b)(共有n－1个(a｜b))对应的任何一个DFA至少有2n个状态。正规式对应的NFA如图2—19所示。确定化求解的状态表如表2—17和表2—18所示。最小化的DFA如表2—19所示。(2)正规式对应的NFA如图2—20所示。确定化求解的状态表如表2—20和表2—21所示。最小化的DFA如表2—22所示。(3)正规式对应的NFA如图2—21所示。确定化求解的状态表如表2—23和表2—24所示。最小化的DFA如表2—25所示。(a｜b)a(a｜b)(a｜b)…(a｜b)(共有n－1个(a｜b))对应的任何一个DFA至少有2n个状态。