村田　真のチャンネル

檜山さんの [「形式言語理論への疑問など」]:http://www.chimaira.org/docs/FLT-Questions.htm を読みました。この記事は、
正規言語の右と左の対称性が教科書の定義から自明
でないことを批判しています。しかし、別の定義では
これは自明なのです。

正規言語の定式化の一つとして、有限モノイドへの準同型
写像への逆像を用いるものがあります。まさに、これが
右と左の対称性を明らかに示した定式化です。

写像（f とします）が準同型であるというのは、

f (uv) = f(u) ・ f(v)

を満たすことです。ここで、uとvは文字列であり、uvはも
ちろんuとvを連結したもので、・ は有限モノイド上での
結合演算です。

文字列の集合Lが正規であるのは、適当な有限モノイドM、
準同型f, Mの部分集合Nがあって、L = {u | f(u) はNに属する }
が成立するときです。

右と左の対称性はこの定義からほとんど明らか
です。Mから、その鏡像である有限モノイドを作ればよく、
あとは自明です。

なお、この定義がそれほど知られていないのは、実装に
向かないからでしょう。