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]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. このグループをキャプチャしたくなく、括弧の後ろに, ,がないため、 (00)andを囲む括弧を削除します。したがって、あいまいさのために必要ありません。(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. 共通のプレフィックスとサフィックスを抽出する[01]*

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