java - 简化正则表达式

Question

我有一个非常简单的问题（双关语）。

这个正则表达式最简单的形式是什么？

(((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))

我正在创建一个正则表达式，它接受包含子字符串 00 和 11 （以任何顺序）的所有二进制字符串的语言。

我现在的表达方式有效，但我确信它可以简化。

Answer 1

这几乎是相同的正则表达式。我只转换了(0|1)into ，在两种情况下共享的左右[01]添加了 a （首先是 11 或首先是 00），并删除了一些不必要的括号：[01]*

[01]*(00[01]*11|11[01]*00)[01]*

---

重现步骤

1. 与

   (((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))
__^^^^^_____^^^^^___^^^^^_____^^^^^______^^^^^_____^^^^^___^^^^^_____^^^^^___

2. 全部替换(0|1)为[01]

   (([01]*(00)[01]*)([01]*(11)[01]*))|(([01]*(11)[01]*)([01]*(00)[01]*)) _______^^^^____________^^^^_______________^^^^____________^^^^_______

3. 删除 and 周围的括号(00)，(11)因为您不想捕获该组，并且括号后面没有*, 。因此，由于模棱两可，它不是必需的。+?

   (([01]*00[01]*)([01]*11[01]*))|(([01]*11[01]*)([01]*00[01]*))
_^____________^^____________^___^____________^^____________^_

4. 删除更多不能解决任何歧义的括号：

   ([01]*00[01]*[01]*11[01]*)|([01]*11[01]*[01]*00[01]*)
________^^^^^^^^^^_________________^^^^^^^^^^________

5. Collapse [01]*[01]*into [01]*which 意思完全一样。

   ([01]*00[01]*11[01]*)|([01]*11[01]*00[01]*)
_^^^^^_________^^^^^___^^^^^_________^^^^^_

6. 提取公共前缀和后缀[01]*

   [01]*(00[01]*11|11[01]*00)[01]*