正则表达式(a|b)*与(a*b*)*是否等价?请通过构造最小DFA说明理由.

Question

正则表达式 (a|b)* 与(a*b*)* 是否等价?请通过构造最小DFA说明理由.

Answer 1

(a|b)*和(a*b*)*从匹配的结果来看是相同的,但是从性能[捕获及反向引用]上来说是不相同的!
(a|b)*此表达式能够匹配a和b任意组合的字符串,因为(a|b)*如果展开表示则为(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b).
(a*b*)*些表达式能够匹配a和b任意组合的字符串,因为(a*b*)*展开表示则为(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*)(a*b*).
应该很好理解!