如何判断正则表达式的等价？
Regular Expressions Equivalence
1. Construct NFA-lambdas corresponding to each RE using Kleene's theorem
2. Construct DFAs for each using the subset/powerset construction
3. (optional) Minimize the DFAs using a standard DFA minimization algorithm.
4. Construct DFAs for L(M1) \ L(M2) and L(M2) \ L(M1) using the Cartesian Product Machine construction
5. (Optional) Minimize these CPMs.
6. Determine whether each one accepts any strings by testing all strings over alphabet E of size no greater than |Q| (works due to the
pumping lemma for regular languages)
虽然从理论上已经解决了这个问题，但是从计算的⾓度甚⾄⼿算的⾓度来看，这个⽅法的结果并不能让⼈
满意。可以说语⾔本⾝的计算依赖于⾃动机由来已久，语⾔本⾝的计算却没有发展起来。所以不断有研究从不同的⾓度，甚⾄单独从正则表达式空间上定义的⼀系列运算出发，来验证正则表达式的等价性，⽽不必将运算映射到DFA空间上去。从数学的⾓度上看，这样⼀系列理论的完善是简洁和优美的，这使得正则表达式空间能够是⾃闭和完备的，重要的结论可以通过该空间本⾝的性质直接推出，⽽不需要DFA的辅助。这样的⽅法也是易于理解，符合⼈们在学习⼀个新的代数结构的⼀般过程。有些时候，这些⽅法的完善甚⾄是计算有利的。相关的⼯作可以参看论⽂Testing the equivalence of regular expressions [].
作为抛砖引⽟的例⼦，这⾥给出⼏个著名的正则表达式的等价的例⼦，这些例⼦在⼀般性的正则表达式的化简上有⼀定的经验作⽤。
\[(a^*b)^* = \varepsilon\ \lvert\ (a\lvert b)^* \tag{1} \]
\[(ab)^* = \varepsilon\ \lvert\ a(ba)^*b\tag{2} \]
\[a^*(a\lvert b)^* = (a\lvert b)^*a^* = b^*(a\lvert b)^* = (a\lvert b)^*b^* = (a\lvert b)^*\tag{3} \]正则化判别分析

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。