「7の倍数」を表す正規表現

スクリプト系の言語を扱う上ではほぼ欠かせない「正規表現」ですが、どんなことができてどんなことができないのでしょうか。

なお、正規表現エンジンによっては再帰や後方参照など、数学的な「正規表現」から外れたものを書けるようになっていることもありますが、今回はそれを考慮に入れないものとします¹。

正規表現→DFA

正規表現は、必ずそれと同じ挙動をする有限オートマトン（有限個の状態があって、それを遷移していくもの）があります。正規表現の3演算である連接・選択・繰り返しについて有限オートマトンに直せるので、それらをつないだものである正規表現も有限オートマトンとなります。さらに、有限オートマトンは、文字ごとに移動先が決まっている「決定性」有限オートマトンに変換できるので、正規表現から対応する決定性有限オートマトン（DFA）を生成できます。

言葉で説明するより図で見たほうがわかりやすいと思いますので、正規表現をNFA、DFAに変換してくれるサイトを紹介しておきます。いろんな正規表現を打ち込んで、眺めてみてください。

また、有限の長さで終わるものは正規表現で表せるのが自明なので²、以下では基本的に、無限に続きうるものを考えていきます。

DFAにして見えること

無限の文字列を有限のDFAに押し込んだことで、見えるようになってくる特徴があります。

まず、受理状態（正規表現が満たすもの）とそうでないものを、DFA上ではかんたんに入れ替えることができます。そしてDFAを正規表現に戻すこともできますので、正規表現の否定も正規表現、ということが導けます。

また、正規表現の処理中に取る「状態」の数も、オートマトンの状態数以上にはなりえない、ということになります。数学的に厳密に表せば、「ある言語が正規言語であることと、その言語の右同値類³が有限個であることは同値」という、「マイヒル–ネローデの定理」となります。

正規表現にできないこと

つまり、状態の数が有限に収まらないものは、正規表現で表せない、ということになります。いちばんわかりやすい（そして、実際的にも重要な）例を挙げると、「左右のかっこの対応が取れた」言語というのがあります。無限のかっこの対応を処理しようとすれば、当然ながら無限の状態が必要となって、「有限」オートマトンではなくなってしまいます。

同値類、ってことは…？

オートマトンで書けば比較的わかりやすいパターンとして、「整数のあまり」というのが考えられます。つまり、「○の倍数」というのも正規表現で表せてしまうのです。ABNFから正規表現を作るabnfというgemがあったのですが、7の倍数のパターンを書いてみると、メモリ使用量が発散してしまって、まともな結果は得られませんでした。そこで、有限オートマトンを再現して、そこからパターンを削っていく（$x$の状態を削減するために、$a\to b$を$(a \to x^* \to b)|(a\to b)$に置き直す）方法を取ることで、7の倍数のパターンを生成させることができました。

生成に使ったRubyスクリプト

NUM_STATES = 7
states = Array.new(NUM_STATES) { [] }

BASE = [/[07]/, /[18]/, /[29]/, '3', '4', '5', '6']

7.times do |from|
  7.times do |to|
    states[from][to] = BASE[(to - 10 * from) % 7]
  end
end

(NUM_STATES - 1).downto(1) do |n|
  n.times do |i|
    n.times do |j|
      states[i][j] = Regexp.union(
        states[i][j],
        /#{states[i][n]}#{states[n][n]}*#{states[n][j]}/
      )
    end
  end
end

p /\A#{states[0][0]}+\z/

いちおう出力結果を下に出しておきますが、尋常ではなく長いです。注意しましょう⁴。

/\A(((((([07]|(6[29]*3))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))|((((3|(6[29]*6))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((5|(4[29]*3))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))))|((((([29]|(6[29]*5))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((3|(6[29]*6))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))((((3|([07][29]*5))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))*(((([18]|([07][29]*3))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((5|(4[29]*3))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))))))|(((((([18]|(6[29]*4))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))|((((3|(6[29]*6))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((6|(4[29]*4))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))))|((((([29]|(6[29]*5))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((3|(6[29]*6))|((5|(6[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((4|(6[29]*[07]))|((5|(6[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))((((3|([07][29]*5))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))*(((([29]|([07][29]*4))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((6|(4[29]*4))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))))))(((((5|(3[29]*4))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))|(((([07]|(3[29]*6))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((6|(4[29]*4))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))))|(((((6|(3[29]*5))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|(((([07]|(3[29]*6))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))((((3|([07][29]*5))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))*(((([29]|([07][29]*4))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((6|(4[29]*4))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((3|([18][29]*4))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([07]|(5[29]*4))))))))))*(((((4|(3[29]*3))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))|(((([07]|(3[29]*6))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((5|(4[29]*3))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))))|(((((6|(3[29]*5))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|(((([07]|(3[29]*6))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([18]|(3[29]*[07]))|(([29]|(3[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))((((3|([07][29]*5))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*((([07]|(4[29]*5))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((4|([18][29]*5))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([18]|(5[29]*5))))))))*(((([18]|([07][29]*3))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))|((((4|([07][29]*6))|((6|([07][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|(((5|([07][29]*[07]))|((6|([07][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))((([18]|(4[29]*6))|((3|(4[29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*((5|([18][29]*6))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*([29]|(5[29]*6))))))*(((5|(4[29]*3))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))|((([29]|(4[29]*[07]))|((3|(4[29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))((6|([18][29]*[07]))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(3|(5[29]*[07]))))*(([29]|([18][29]*3))|(([07]|([18][29]*[18]))(4|(5[29]*[18]))*(6|(5[29]*3))))))))))))+\z/

結論

• 想像以上に正規表現は強力
• でも、あるリミットを越えると実用性に乏しくなる

1. こうした拡張がある場合、文脈自由文法も表せるようになりますが、無限ループが発生し得るなど、純粋な正規表現とは性質的にも違ったものとなります。 ↩

2. 実用的になるかはともかく、起きうるパターンをすべて連ねて選択をかければ、正規表現となります。 ↩

3. その正規表現について、「右側に何をつければ正規表現が受理する文字列になるか」を基準に文字列を分類したもの。 ↩

4. これでも、正規表現展開の都合上入る?-mix:や、([07])の外側のかっこなど、不要なものは多少除去しています。 ↩