5-20 正規表現でブール代数の公式

正規表現パズル

正規表現とブール代数の公式についての考察です。


補元法則その1
  _
A+A = 1

(?=A)|(?!A) は、全ての位置にマッチ


補元法則その2
  _
A*A = 0

(?=A)(?!A) は、どの位置にもマッチしない


交換法則その1

A+B = B+A

(?=A)|(?=B) と
(?=B)|(?=A) は、同値である。

下記のような、肯定先読みでの、括弧と\1や\2などの組み合わせは考慮してません。(他の法則も同様)

(?=(X+))|(?=(Y+)\1)
(?=(Y+)\1)|(?=(X+))


交換法則その2

A*B = B*A

(?=A)(?=B) と
(?=B)(?=A) は、同値である。


分配法則その1

A*(B+C) = A*B + A*C

(?=A)((?=B)|(?=C))    と
(?=A)(?=B)|(?=A)(?=C) は、同値である。


分配法則その2

(A+B) * (A+C) = A + B*C

((?=A)|(?=B))((?=A)|(?=C)) と
(?=A)|(?=B)(?=C)           は、同値である。


ドモルガンの法則その1
___   _ _
A+B = A*B

(?!(?=A)|(?=B)) と
(?!A)(?!B)      は、同値である。

正規表現でブール代数を使う時は、
全体の否定を使わないほうが可読性が高いようです。


ドモルガンの法則その2
___   _ _
A*B = A+B

(?!(?=A)(?=B)) と
(?!A)|(?!B)    は、同値である。


吸収法則その1

A+ A*B = A

(?=A)|(?=A)(?=B) と
(?=A)            は、同値である。


吸収法則その2

A* (A+B) = A

(?=A)((?=A)|(?=B)) と
(?=A)              は、同値である。


回帰法則(二重否定)

=
A = A

(?!(?!A)) と
(?=A)     は、同値である。


便利な公式
    _
A + A*B = A+B

(?=A)|(?!A)(?=B) と
(?=A)|(?=B)      は、同値である。