soutaroにっき

後輩 2007/05/17 08:37 いえ、任意のオートマトンにはそれと等価な正規表現がありますから、特に制限はなかったりしますよ。

soutaro 2007/05/17 11:04 うん。いや、そうじゃなくて、一応それはわかってるんだけど、正規表現になってた方が取扱いが簡単だと言いたかったわけで。/a(bc)*d/から例を作るのは簡単だけど、これと等価なオートマトンだと、どこにループがあるのかわからなくてちょっとめんどくさくない？

soutaro 2007/05/17 11:12 じゃないな。オートマトンから正規表現を作るのといっしょか…
んーでも、よく知らないからいいやｗ

k.inaba 2007/05/17 14:07 オートマトンの上を始状態から終状態にたどりつくまでランダムウォーク、でどうでしょうか。確率的にそのうちループからも出てきます。（あるいは、生成中の例が長くなりすぎたら深さ優先探索なり最短路探索なりで終状態まで慌てて全力疾走するようにするとか）

soutaro 2007/05/17 22:39 >オートマトンの上を始状態から終状態にたどりつくまでランダムウォーク

最初それを考えていたんですが、長すぎた場合とかを考えてちょっと手がとまってました。深さ優先探索すれば良いじゃんというのは、その通りですね。でも、naiveな深さ優先探索や最短路探索だと、なんかお尻の方が、決定的になりそうでちょっと嫌かもしれません。

あとはNFAをDFAに変換しないと、でも面倒…とか考えてたんですが、よく考えたらそれはランダムウォークだと必要ないですね。うーむ。