正則表現のメモ

 正則表現(正規表現に同じだけど、形式言語においては正則表現と呼んで、実際にプログラミングで使うようなのは正規表現と呼んだりしている)の等式における性質がわかりづらかったので解釈をメモ。以下、正則表現r,sが集合L(r),L(s)を表すとする。記号の定義は、
 (r+s) = L(r){\cup}L(s) (和集合、orだと思えばよい)
 (rs) = L(r)L(s) (言語の積は各要素の連結要素の集合)
 (r^{*}) = L(r)^{*} (集合の閉包、空文字を含む自由な繰り返し)
性質としてはだいたい次が挙げられる、みたい
 r^{*} = {\epsilon} + r + rr + rrr + ...
 r^{*} = r^{+} + {\epsilon} (r^{+}は一度以上の繰り返し)
 ({\epsilon}+r)^{*} = r^{*}
 (r+s)^{*} = (r^{*}s^{*})^{*}
 (rs)^{*} = r(sr)^{*}
 (rs+r)^{*}r = r(sr+r)^{*}
変形の確認を。
 (rs)^*r\\
 = r + rsr + rsrsr + rsrsrsr + ...\\
 = r(ε + sr + srsr + ...)\\
 = r(sr)^{*}
 (rs+r)^{*}r\\
 = (r^{*} + (r^{*})rs(r^{*}) + (r^{*})rs(r^{*})rs(r^{*}) + ...)r\\
 = r^{+} + (r^{+})s(r^{+}) + (r^{+})s(r^{+})s(r^{+}) + ...\\
 = r(r^{*} + (r^{*})s(r^{+}) + (r^{*})s(r^{+})s(r^{+}) + ...)\\
 = r(sr+r)^{*}