テキスト処理のための正規表現に計算理論はあるのかな

なるほど。これはおもしろい。

正規表現で素数判定

「C言語で素数判定」や「Rubyで素数判定」はそうでもないのに、「正規表現で素数判定」と言われるとおもしろいと思うのはなぜだろう。

4320122070計算の理論について勉強したことのある人は皆、正規表現で素数を記述することはできないことを知っている(たとえばSipser『計算理論の基礎』を参照)。だから、「正規表現で素数判定」と言われると、一瞬不思議な感じがするのだろう。

正規表現の表現力はもともとそんなに高くない。だから、

正規表現とは元々数学の概念だけあって、数学の問題を解くのにもってこいですね!(regexp – でエラトステネスのふるい)

なんていうのは、かなりミスリーディングなジョークだ。

とはいえ、テキスト処理のための正規表現は、計算理論における正規表現よりもかなり強力なものになっている。その原因の一つに、括弧でくくられた部分文字列を参照するために「\数字」という記法が導入されたことがあり、今話題にしている素数判定を可能にしたのも、この記法だ(拙著『Webアプリケーション構築入門』でも違いを強調している)

大事なことだから繰り返す。計算理論の正規表現では、素数判定はできない。テキスト処理の正規表現では、素数判定ができる。

素数判定というと、次のようなものをそうぞうする。

sub isPrime {
  my $n=shift;
  my $imax=sqrt($n);
  for (my $i=2; $i<=$imax; $i++) {
    if ($n % $i == 0) { return 0; }
  }
  return 1;
}

たとえば、isPrime(5)を評価すれば、5が素数かどうかがわかる。

これと同じことを、1を5個並べた文字列に対するマッチング「’11111′!~m/^1?$|^(11+?)\1+$/」で調べられる。

なるほど。これはおもしろい。

さて、素数判定には、「エラトステネスのふるい」という有名な方法がある。

「2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20」という数列が与えられたときに、2の倍数を消去、3の倍数を消去、・・・としていくと、素数列つまり「2,3,5,7,11,13,17,19」が残る。

今話題にしている記法では、「11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111,11111111111111111,111111111111111111,1111111111111111111」という文字列が与えられたときに、「11,111,11111,1111111,11111111111,1111111111111,11111111111111111,1111111111111111111」が残るといい。

正規表現でエラトステネスのふるいはさすがに無理かな(正規表現で素数判定)

という問いで期待されている解答は、次のようなものなのだろう。

これと同じことを、「・・・」という文字列に対する置換「’・・・’=~s/???/???/」で調べられる。

最初に思いついたのはこんなもの。

#!/usr/bin/perl -w
use strict;
use warnings;

my $max=shift || 20;
my $nums=join ',',map {'1' x $_} (2 .. $max);
print "$nums\n";

while ($nums =~ m/(^|,)(1+)(,|$)/) {
  printf "$2,";
  $nums=~s/(^|,)($2)+(,|$)/,/g;
}

これは、理想の形式からはほど遠い。whileなんてものを許したら、表現力が正規表現と比べてどうなのか、まったくわからなくなってしまうのだから。