無限について考える

ModernCompilerImplementationInCのLexerの章を読了。後でやろうと思って演習問題を見ていたら、正規表現関係でこんな問題があった。

For each of the followings, explain why you're not surprised that there is no regular expression defining it.

正規表現は無限の長さの文字列を含む言語を記述可能なのは明らかだけど、正規表現には扱えなくて他の表現では扱える無限があるのもまた明らかだ。例えば、正規表現では括弧の入れ子になった文字列は解析できないけど、そのような文字列を解析する方法はいくらでもある。

つまり、無限にもクラスがあり、少なくとも正規表現で記述できる無限（正規言語）と、そうでない無限がある。その違いを作り出しているのは何だろう、ということについて考えてみた。おそらくそういうことは、数学者や計算機科学者たちが考えつくして、定式化され明らかになっている事も多いとは思うけど、自分のイメージを膨らませることは答えが見えなくても楽しいものだ。

無限のクラスを考えるには、無限の源について考えてみるのがよいのではないか。無限を生み出す方法として真っ先に考えられるのが、再帰と反復。正規表現の無限を生み出しているのはクリーネ閉包（0個以上を表す * のこと）。クリーネ閉包は、おそらく反復と等価。

反復と再帰はどちらが強力かというと、再帰のほうが強力だろう。反復に無限のスタックが加われば、再帰と同じことができる。正規表現は無限のスタックに相当するものが無いから、再帰的な文字列の解析ができないのかなぁ。

そんなような事を考えていた。眠たくて思考がまとまらない、、、眠たくなくてもまとまらんだろうけど。