正規表現パターンに対して次が成立します。
- (A | B)* = (A*B)* (A*)
AとBは任意のパターン、イコールは「左辺にマッチする文字列は右辺にもマッチし、右辺にマッチする文字列は左辺にもマッチする」という意味。
もう少し一般的な文脈では、これをコンウェイ（Conway）の和スター公式（sum-star equation）と呼びます。右辺の「|」を「+」に書き換えると、(A + B)* なので、和とスターの組み合わせから和を除く手順だと思ってもいいでしょう。
この和スター公式は憶えにくいし、憶えても忘れる。そこで、具体的で馴染みのある例を考えました。
DataChar ::= [-_a-zA-Z0-9]
DelmChar ::= [, ]
EndOfData ::= [.\n] /* 注：[]のなかでは\.としなくてもよい。 */
区切り文字を「コンマまたは空白」として、データ項目（フィールド）を並べたデータ表現（レコード）を考えます。レコードの終わりはピリオドか改行です。
Item ::= DataChar* DelmChar
Record ::= Item* EndOfData
別に不思議はないですよね。次はレコードの例です。
hello_world,123 456, Apple,.
項目に区切ると、"hello_world", "123", "456", "", "Apple"の5項目です。Appleの直前の空白により空な項目が1つ生まれてしまったのです。全部コンマで書けば事情がわかりやすいでしょう。
hello_world,123,456,,Apple,.
Appleの直後のコンマも気になりますが、このコンマも含めて項目なので省略できません。最後の区切り文字は省略可能だとすると次の定義となります。
Record ::= (DataChar* DelmChar)* DataChar*
(DataChar* DelmChar) が最後に区切り文字を持つ項目、DataChar* が区切り文字を持たない最後の項目です（これはなくてもよい）。今定義したRecordの構文をもとに、構文チェッカーを作りましょう。先頭からピリオドまたは改行までの文字列が“構文的に正しいレコード”かどうかを判定するプログラムです。
んん、 待てよ。
“構文的に正しいレコード”って、実は何だって正しくなってしまうのでは？
データ文字でも区切り文字でもない変な文字が出てこない限りは、どんな文字列でも“構文的に正しいレコード”となります。ちょっと考えればわかりますよね。つまり、実は次の定義でも同じこと。
Record ::= (DataChar | DelmChar)*
正規表現パターンとしての効果が同じことをイコールで示すなら：
(DataChar | DelmChar)* = (DataChar* DelmChar)* DataChar*
はい、これが冒頭で示した和スター公式の例です。
[追記]
正規表現を普通っぽく /(a|b)*/ のように書くとして、/(a|b)*/ == /(a*b)*a*/ のような等式を使えるプログラミング言語はないと思いますよ。等式の判定ができないわけじゃないけど、やるとするなら次のどちらかでしょう。
- 正規表現から標準化（canonicalize）されたオートマトンを作って、オートマトン構造（辺ラベル付き有限グラフ）が同等（isomorphic）であるかどうか判定する。
- 正規表現の代数（クリーネ代数）は、ホーン等式の公理系を持つので、ホーン等式的推論系を作り、与えられた等式をこの推論系に証明させる。
2番目のほうは、現実的に可能かどうかは知りません。いずれにしても、/(a|b)*/ == /(a*b)*a*/ を使う場面や需要がないでしょう。
[/追記]
