数学における "regular" と "normal"、「正則」と「正規」のオートマトン理論との関連について

追記：個人的な調べものの一部です。いろいろ言葉遣いとかがわかってない感じに微妙なのはご容赦ください。オートマトン理論の本職の研究者の方が面白いネタエントリの材料にしてくださったので調べた甲斐がありました。
数学、特に解析学における “regular” および日本語の「正則」は、実連続関数の smoothness すなわち derivabilityに関わる文脈で使われることの多い語である。これは当該関数が多項式で表現可能であるか、少なくともテイラー展開(形式的冪級数による表現)可能であることを示しているものと解される。複素関数論での「正則」は “holomorphic” の訳語で、これは幾何学的な観点から見た analyticity つまり無限回微分可能性のことである。

有限オートマトンを定義する “regular expression” は、文字列半群上で定義される一種の「冪級数」とみなせる。文字列(たとえば “abc”)によって正則表現(たとえば /abca(x|y)z/)を「左から微分」した結果が、新たな正則表現(たとえば /a(x|y)z/)であると捉えることができる。これはさきほどの、「和積形」で書かれた正規表現を等価な「積和形」に書き換えるとわかりやすい。
/abca(x|y)z/ は /abcaxz|abcayz/ と等価であるが、これを “abc” で「左から項別微分」して　/axz|ayz/ を得る。これは/a(x|y)z/ と等価である。閉包、すなわち Kleene Star については、指数関数を多項式で表現できないように、「積和形」による表現は無限に長くなるものの、上記の「左からの微分」の議論は成立する。たとえば /a*/ は /ε|a|aa|aaa|…/ となり(εは空文字列)、文字列 ”aaa” で「左から項別微分」しても変わらず /a*/ のままである(cf. Brzozowsky[1964]、ただし実例は筆者の解釈に基づく)。

以上の議論は一応有限オートマトンを定義する表現の「正則性」をサポートするものになっている。ただし、Kleene は研究の初期においては、regular expression に独立した概念としての地位を与えていない(Kleene[1951])。また、そもそも時間の経過に伴って生起する出来事を “regular events” と名づけた理由についてKleene はこれに明確な説明を与えていないように思われる。

なお、この正規表現の「微分可能性」は、Ken Thompson、Doug McIloy らによるIBM7090 上の QED エディタ、および UNIX の grep コマンドにおける正則表現の応用の基礎理論となっている(Thompson[1968])。

「正規」という単語は一般に “normal” “genuine” “canonical” などの単語の訳語であり、特に　“regular” との対比では “normal” の訳語と解するのが適切であろうと思われるが、オートマトン理論の数学的な定式化における、”normal” の役割は、定かでない。一般に ”regular” には「普通」、”normal” には「模範的」という含意があり、特に位相空間論における “normal” は “regular” よりも強い条件を示す。すなわちある開集合族が “normal” であれば同時に “regular” である。