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

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

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

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

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

　なお、オートマトンの日本語訳は、自動機械であって、自動羊肉ではないらしい。