Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

正規表現エンジンを作ろう(1)

CodeZineさんで連載を始めました。全6回でDFAエンジンの実装方法を紹介する予定なので、興味のある方はぜひ*1

ところで、第一回で出て来た /^([a-z]*)\1$/ と言う正規表現ですが、

 残念なことに、数学的な3つの定義ではこの正規表現が表す文字列集合を表現できません。このことは数学的に証明も可能です。

と書きました。この証明をするには、正規言語のポンピングレンマってのを使います。

証明

この正規表現が表す言語が、正規言語であると仮定します。ポンピングレンマより、p≧1がポンピング長pが存在します。

このpに対し、長さがp以上である、a..(p個)..aba..(p個)..abと言う2p+2の長さの /^([a-z]*)\1$/ にマッチする文字列を考えます。ポンピングレンマより、この文字列はある XYZ と言う三つの部分文字列にわけられて、ポンピング補題の3条件を満たすはずです。

ここでまず、XYZは2つの条件である |Y| > 0 と |XY| ≦ p を満たしています。この時、 a..aba..ab の最初のp 文字は a であるため、XY は全てaからなります。特に、Yが aを1文字以上繋げたものであることに着目して下さい。

ここで XYYZ と言う文字列を考えると、この文字列は、 a..(p個より多い)..aba..(p個)..ab となってしまうため、/^([a-z]*)\1$/ にマッチしません。つまり、 ポンピングレンマの最後の条件が i=2 に対して成立する・・・つまり、 XYYZ ∈ /^([a-z]*)\1$/ が成り立たなければいけないことに矛盾します。

以上から背理法により /^([a-z]*)\1$/ は正規言語ではありません。

参考文献

計算理論の基礎 [原著第2版] 1.オートマトンと言語
太田 和夫 田中 圭介 阿部 正幸

4320122070
共立出版 2008-05-21
売り上げランキング : 43388

Amazonで詳しく見る
by G-Tools

*1:ただし、動作を理解するのが目的の実装ですので実用性はないですw