「0がn個続いたあと1がn個続く」を正規表現にできるか?

こんにちは。前回に引き続きたぬきです。
週次LTの担当ということで、計算機科学の基礎を紹介してみました。

「0がn個続いたあと1がn個続く」を正規表現にできるか? from tanukingUb

切り口として、正規表現まわりをやってみることにしました。Uzabaseは情報プラットフォームサービスSPEEDAを展開しており、どのエンジニアもデータベース周りの知識を持っているため、正規表現は慣れ親しんだものの１つであるからです。

具体的な問題として、「0がn個続いたあとに1がn個続く」を正規表現にできるか？をテーマとしました。

お話の流れとしては、(1) 正規表現は有限オートマトンに変換可能、(2) 有限オートマトンには必要条件がある、(3) 上述の問題は有限オートマトンの必要条件を満たさず、正規表現にはできない、という流れです。

ポンピング補題

オートマトンの復習および「(1) 正規表現は有限オートマトンに変換可能」については、文章よりスライドを見てもらえば十分かと思いますが、「(2) 有限オートマトンには必要条件がある」「(3) 上述の問題は有限オートマトンの必要条件を満たさず、正規表現にはできない」については口頭で話した部分を補足したいと思います。

(2) 有限オートマトンの必要条件のひとつに、ポンピング補題というものがあります。ある有限オートマトンの状態数をpとすると、そのオートマトンに認識される（受領される）文字列のうちp以上の長さの文字列は必ずポンピング補題の3条件を満たします。

条件のうちの1番目「各i≧0についてx(y^i)z∈A」についてもう少し意味を補足しましょう。まずAはある有限オートマトンが認識する（受領する）文字列の集合です。また、x(y^i)zとは、文字列xの後に文字列yが0回以上繰り返し続き、最後に文字列zがあるということです。つまり、1番目の条件は、ある有限オートマトンに認識される文字列は必ず、x(y^i)z∈Aを満たす文字列x, y, zにわけられるという意味になります。

ポンピング補題の証明は、スライドに記述した迷路のような図でも直感的に理解できるかもしれませんが、より詳しい証明は後述の本を御覧ください。

さて(3)に入り、「0がn個続いたあとに1がn個続く」がポンピング補題を満たすか調べてみましょう。もし「0がn個……」を満たす有限オートマトンがあるとすれば、その条件を満たす文字列で長さp以上のものはすべてポンピング補題を満たすはずです。

ここで、0がp個続いたあとに1がp個続く文字列sを考えてみましょう。sは明らかに「0がn個……」を満たします。またsは長さp以上なのでポンピング補題も満たすはずです。つまり「各i≧0についてx(y^i)z∈A」も満たすはずですが、どんなyならばそんな条件を満たすでしょうか？

実はその条件を満たすyは存在しません。もしyが0からだけ成るとすると、i≧2では文字列に含まれる1の数よりも0の数が多くなってしまい、Aに含まれることができません。yが1からだけ成るとしても同様です。あとはyが0と1から成った場合だけですが、この場合、yが連続すれば0の前に1が出てきてしまうため、やはりAに含まれることができません。よって、いかなるyも条件を満たしません。

以上のことから背理法により、「0がn個……」は有限オートマトンでないことが示されました。よって「0がn個……」は正規表現にできません。

まとめ

LTの時間的な制約から正確な定義などを説明せずに話を進めてしまいましたが、正確な定義や証明を理解していくと、とてもシンプルかつ奥深い世界に触れることができます。スライド内でも簡単に紹介していますが、下記の本がオススメです。

計算理論の基礎 [原著第2版] 1.オートマトンと言語