授業準備で本を読んでいて，気になる記述があったので，ちょっと紙と鉛筆を使って求め，Rubyで確認してみました．たぶん間違いないはず．
#!/usr/bin/env ruby class REMatch def initialize(pattern_string) @pattern_string = pattern_string @pattern = Regexp.new(pattern_string) @maxlen = 8 end def match(n) 0.upto(2 ** n - 1) do |i| str = sprintf("%0*b", n, i) if @pattern =~ str puts " #{str}" end end end def start puts "\"#{@pattern_string}\" matches:" 1.upto(@maxlen) do |i| match(i) end end end if __FILE__ == $0 pattern_string = "^(0(11)*0|(1|0(11)*10)(00|01(11)*10)*(1|01(11)*0))*$" REMatch.new(pattern_string).start pattern_string.tr!('01', '10') REMatch.new(pattern_string).start end
実行結果*1を見れば，何をしているかは十分に想像できると思いますが，解説は必要ですね．
プログラムについて
本というのは『オートマトン言語理論 計算論〈1〉 (Information & Computing)』です．以下，脚注はこの本のページ番号です．
上のプログラムは，「0と1をいずれも偶数個持つ文字列*2」について，@maxlen以下の長さのものを全て出力します．ただし空文字列は出力しません．
正規表現では難しそうですが，有限オートマトンで考えると，
- 0と1をいずれも偶数個持つ文字列を読んだ状態
- 0を奇数個，1を偶数個持つ文字列を読んだ状態
- 0と1をいずれも奇数個持つ文字列を読んだ状態
- 0を偶数個，1を奇数個持つ文字列を読んだ状態
の4つの状態を用意し，次に0か1を読むときに，どの状態に移動するかを考えれば，対称形の状態遷移図a symmetric state transition diagramが描けます*3．
そして次に，任意の有限オートマトンに対して，それを正規表現に変換するアルゴリズムを適用して，正規表現を求めればいいのです．状態消去法*4を用いる際，消去する状態の選び方次第で，最終的な正規表現が異なってきますが，対称性から，一つの方法で求めた正規表現の，0と1を入れ替えてもいいはずで，実際，上のプログラムで，同じ出力になることを確認できます*5．
