正規表現１（クリーネ代数で遊ぶ）
このページはマス旅の一部です。
正規表現は慣れていない人が多いため嫌われがちだと思います。
でも、その複雑怪奇なルールを探求すると
意外なことに、数学とのつながりが凄く強いことがわかってきますよ。
その歴史とルールを調べることで、暗記ではなく、遊びの道具にしましょう。
１．数学外の知識
表現というものを日常言語であれ、数式であれ、プログラミング言語であれ
「記号を色分けすること」から理解できるようになります。
それは正規表現でも同じこと。
日常言語ならば、名詞、動詞、形容詞、副詞などに色分けしたり、
句と節とかの区切りのコトバなどがありますね
数式ならば、定数、変数、数字、演算、関数、
演算用の添え字（上、下）、不等号などと色分けしますね。
正規表現も色分けが大事です。
普通の記号、普通にする記号、一般記号、抽象記号、まとまり記号、論理的な記号などなど。この言葉遣いはzenの勝手な色分けですが、素人目線の方がわかりやすい場合も
あるでしょうから、お付き合いください。
正規表現は、検索・置換が主な用途です。
つまり、探したい表現をそのままかくのではなく、少し広げて書くこと、
そして、広げて探して終わりではなくて、
探しあてた表現の部分を、意図的に置換したりするときに使われます。
特定のプログラミング言語に依存しないでかきたいので、
検索対象表現はシングル引用符でくくり、正規表現はダブル引用符にして、それを
'1','2','3'←"123"のように書くことにします。
＜１文字を探す＞
まずは1文字検索からいこう。
その用途に使えるのが、
ドット(.)ハイフン(-)かっこ（[],()）です。
（正規表現の予約文字をメタ文字(メタキャラ）と言います。）
普通に１文字が並んだものは、ジャストそれだけを探します。
'a'←"a"
'A'←"A"
ドットは数字以外の一文字の代用です。たとえばこうです。
'make','take','fake','@ake',.... ←".ake"
でも、広すぎますね。
makeとtake
だけを拾いたいなら、
1文字集合を大かっこでくくるか、
パイプラインで区切って小カッコでくくります。
'make','take'←"[mt]ake"
'make','take'←"(make|take)"
この中くらいの書き方もあります。１英小文字だけとか、１英大文字だけとか、１数字だけとかならんでもよいという場合です。
'aake','bake','cake','dake',..,'zake'←"[a-z]ake"
'Aake','Bake','Cake','Dake',..,'Zake'←"[A-Z]ake"
'0ake','1ake','2ake','3ake',..,'9ake'←"[0-9]ake"
メタ文字を普通の文字に使いたいときもあるでしょう。
バックスラッシュ(\)が前につくと、普通の文字になりますね。
'3.14'←"3\.14"とかくのですね。小数をふつうに探すときは小数点の前に\をつけることになるんだね。
バックスラッシュ(\)のもっと別の使い方もあります。
文字の普通名詞化のようなもんです。
[0-9]とかくかわりにdigitという意味で\dが数字です。なぜか\Dが数字以外です。
spaceの意味で、\sが空白（スペース、タブ、改行）を、\Sが空白以外を指します。
＜連続するかも＞
SQL文やクラス図を作るときに、個数範囲を0以上、1以上で表す記号もあります。
これは便利ではあるけど、見た目と違うものが引っかかるので要注意です。
クエスチョン(?),アスタリスク(*),プラス(+)
あるかも記号（?）はあとにつけます。
"20000?円"→'2000円','20000円'
"Mac ?OS"→'Mac OS','MacOS'です。これは便利だね。
もっとすざまじい記号があります。
x*はxが0個以上、x+はxが1個以上です。
"20*円"←'2円','20円',...'2000000円',.....
"20+円"←'20円',...'2000000円',.....
連続のさぼり表記もありますよ。
2千万円は0が7個と分かっているけど、0の連続記述をさぼりたいなら、
{回数}と中カッコを使います。
"20{7}円"←'20000000円'でOKです。
＜アンカー記号＞
^は先頭、$は末尾の表示で使われます。
[^abc] のように大かっこの先頭につけると「abc以外の1文字」という否定の意味になります。
＜キャプチャグループの参照番号が検索終了条件となる＞
事前に()で囲まれた部分正規表現（グループ）に対して
\1はグループ１として展開されます。
"^(.).*\1+"
は^(.)が後ろで\1として展開されて、+があるため、あるだけ範囲を貪欲に取り出します。
どこからどこまで取り出せるかを順序立てて見ていきましょう。
'abcdefghaaabb'⇒
"^(.)"は先頭文字aを受け取ります。
'abcdefghaaabb'⇒[a]
".*"があるので、途中の文字を"\1+"=a連続まで読み取ります。
'abcdefghaaabb'⇒[abcdefgh]
"\1+"でaaaまで読み取ります。
'abcdefghaaabb'⇒[abcdefghaaa]
２．数学の支援
さっきまでは、正規表現の例を紹介しました。
さて、正規表現の始まりは意外なことに、あまり、広くは語られていないようです。
1940年代にアメリカの数学者クリーネの発案です。
正規集合、正規表現という文字集合のルールを考えたそうです。
これをクリーネ代数といいます。
＜クリーネ代数＞
文字列の集合をΣとする。
その要素をA,Bとすると、
連結（連接）、つまり積ABも要素だ。
選択、つまり和A|Bも要素になる
要素を０個以上連続したもの(閉包）A*やB*も要素とする。
演算の優先順位は閉包、連接、和の順に強い。
空集合も要素だ。
和の単位元ゼロ（0）は決してマッチしない表現
積の単位元単位元（1）: 空文字列 ^$
a*c|dは閉包、連結、和の順番に読み取れます。
a(b|c)は「a(b+c)」の意味になり、ab|acは「ab+ac」の意味だから、
普通の代数計算の分配法則も成り立つことがわかるね。
たし算とかけ算はできるけど、たし算の逆元はないので
クリーネ代数は「半環」の代数と言われることもあるね。
＜正規表現を数学の道具にする＞
おもしろい例があります。
"^1?$|^(11+?)\1+{{SSR}}quot;で、なんと、
合成数であることが判断できるのです。
分解して、検索の開始と終了条件を見るとわかります。
"^1?{{SSR}}quot;
アンカー^と$にはさまれているので、"1?"のみ、つまり1か空ですね。
"^(11+?)\1+{{SSR}}quot;
検索グループと参照番号でできています。
最後部分は\1+$になっていますね。
\1の代入部分が1回以上繰り返して終了（$）余分なものがない。
では検索グループとなる部分正規表現はどうでしょうか。
^(11+?)は先頭から1が2個以上あるかの検索を、控えめに無欲に探します。
2個、3個、…と長くします。
^(11+)だったら、強欲マッチなのでマッチ範囲を一気に最長のものを貪欲に探します。
しかし、^(11+?)は、マッチする範囲を地道に増やしていきます。
いきなり最長をめざさないのです。
つまり、
この「無欲」ということが
検索が成功するまで繰り返すという「粘り強さ」につながるのです。
具体的な例で試してみよう。
N4="1111"
N5="11111"
N4で"^1?$|^(11+?)\1+{{SSR}}quot;を調べるとどうなるでしょう。
前半"^1?{{SSR}}quot;条件１か空には当てはまらないので、次の｜のあとを確認しましょう。
先頭の'11'=\1にすると、残りが'11'1個反復でヒットしますから、
"^1?$|^(11+?)\1+{{SSR}}quot;には
合格です。
全体4文字が\1がさす2文字で割り切れて合成数になっています。
だから、４は合成数と言えます。
N5の場合はどうでしょうか。
N4と同様に'11'=\1にできますが、5個は2個ずつ切って余るので失敗です。
無欲ですが、あきらめません。
'111'=\1にしてみます。やはり失敗。
'1111'=\1にしても失敗。
'11111'にすると、あと1個入る隙間どころか検索範囲は終わってますから失敗。
最後まで調べたので終了ですね。
だから、合成数テストは不合格です。
「全体5文字が\1がさす文字が2回以上入るものの検索」としての合成数テスト
は不合格だから、素数となるのです。
３．コード化
＜Python＞
import re
# 合成数（2以上の非素数）にマッチする正規表現
# ^1?$ : 0または1
# | : または
# ^(11+?)\1+$ : 2以上の長さの1の繰り返し（約数を持つ）
composite_pattern = re.compile(r"^1?$|^(11+?)\1+{{SSR}}quot;)
def is_prime(n):
# n を '1' の n個の繰り返し文字列に変換してマッチング
return not bool(composite_pattern.match("1" * n))
# 2〜20 の素数判定
for i in range(1, 21):
print(f"{i:2d}: {'素数' if is_prime(i) else '合成数'}")
[出力例]
1: 合成数
2: 素数
3: 素数
4: 合成数
5: 素数
6: 合成数
7: 素数
8: 合成数
9: 合成数
10: 合成数
11: 素数
12: 合成数
13: 素数
14: 合成数
15: 合成数
16: 合成数
17: 素数
18: 合成数
19: 素数
20: 合成数
＜geogebra＞
geogebraには、
正規表現はありませんが、IsPrime(n)という関数が標準で
入っているので、「自前でトリッキーなプログラミングはしなくていいですよ」
というスタンスでしょうね。
タイトル「IsPrimeを使おう」
N=Slider(2,20,1)
text1=If(IsPrime(N)==True,N+"：素数", N+"：合成数")