ええ、そうなの!? と思ったので深追いしてみた。
状態遷移図を書いてみるとこう。
ほんとは1〜15まで全て状態を書いて、ε遷移を加えてεの長さも1とした最少の単語を見付けなければならない。
で、これをこのPDFの方法で正規表現に書き直してみる。だるかったのでfizzはF、buzzはB、fizzbuzzはZにしておいた。
my $reg_inv_fizzbuz = qr/^( (((((F?B)?F)?F)?B)?F)?Z (FBFFBFZ)* (F|FB|FBF|FBFF|FBFFB|FBFFBF) |(((((F?B)?F)?F)?B)?F)?Z |((((F?B)?F)?F)?B)?F |(((F?B)?F)?F)?B |((F?B)?F)?F |(F?B)?F |F?B |F )$/x;
これでfizz buzz の列について回答が存在するか否かは判定できる。ただ、正規表現に変換してしまった時点で各遷移の重み付けの情報は飛んでしまったので、逆fizzbuzzの解答にはならなかった。
おしまい。
【追記】
正規表現は使ってないけど、一応automata的な解答は作っておいた。もっと簡単にかけると思ったら思ったより面倒。