hirax.net::Keywords::「非決定性オートマトン」のブログ



2010-04-20[n年前へ]

正規表現と「美しいコード」 

 しばらく前のことだったと思う。正規表現の書き方の話題になり、「美しいコード」とか「目的に対する実装のバランス」といった話になった。

 その時、「コンパイル(NFA->DFA)にどの程度の時間がかかるか」という観点からのアドバイスを受けた。これまで、そういった基本的なことを考えたこともなかったので、今さらながら、そのアドバイスを消化するために、正規表現とNFA・DFAについて、さらってみた。

 DFA:Deterministic Finite Automaton=決定性有限オートマトン、やら、NFA:Nondeterministic Finite Automaton=非決定性オートマトンといった文字列を眺めながら、こんなワクワクさせられる面白いことを、なぜ今まで楽しむことができなかったのだろうと、そんなことを切実に感じさせられた。

 なお、オートマトンの日本語訳は、自動機械であって、自動羊肉ではないらしい。
 ところで、あなたの「マトン」のイメージは、どんなものでしょう?



■Powered by yagm.net