NFAを正規表現に変換する方法

正規表現をNFAに変換するにはアルゴリズムがあることが分かりました。NFAを正規表現に変換する方法

しかし、NFAを正規表現に変換するアルゴリズムがあるのだろうかと思っていました。ある場合は、それは何ですか？

もしそうでなければ、すべてのNFAが正規表現に変換できるかどうかも疑問です。正規表現が表現できないNFAはありますか？

ありがとうございました！：唯一の初期と最終状態があるまでDここ

2012-02-09 formatjam

正規表現は、そうそこに、*任意*正規言語を表現することができます可能なNFAごとに少なくとも1つの正規表現が存在する必要があります。しかし、私はNFAから私の頭の上の正規表現に行くためのアルゴリズムを知らない。 –

また、あなたのタイミングは実際に不気味です - 私の友人は、今日このクラスの同じ質問を私に尋ねました。私は答えを覚えていませんでした:( –

あなたの質問への様々な答えを参照してください：http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-式 – Masterfool

は、各遷移が増分正規表現に置き換えられるアルゴリズムである。https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]

2012-02-09 05:43:05 buzypi

正しいですが、ノードがたくさんある場合は動作しません。シンプルで少数のノードにはいいですか他の提案はありますか？ –

リンクが死んでいます。 /courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf –

答えて