Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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

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

正規表現→DFA

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

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

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

DFAにして見えること

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

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

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

正規表現にできないこと

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

同値類、ってことは…?

オートマトンで書けば比較的わかりやすいパターンとして、「整数のあまり」というのが考えられます。つまり、「○の倍数」というのも正規表現で表せてしまうのです。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/

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

/\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])の外側のかっこなど、不要なものは多少除去しています。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした