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)转换成[01]，在左右两边共享了一个[01]* (11 开头或 00 开头)并删除了一些不需要的括号:

[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. 删除 (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. 将[01]*[01]*折叠成[01]*，意思完全一样。

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

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

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