2

例：以下のシンボルシーケンスが与えられた場合、

a b c b c d d d b c b c d d d d e

それを受け入れることができる最も単純なDFAは、17の状態のチェーンです。

以下の正規表現は上記のシーケンスを導き出すことができますが、

a (b c)* (d)* (b c)* (d)* e

また、対応する最小DFAには8つの状態があります。

さらに、正規表現a ((b c)* (d)*)* eには、4つの状態を持つさらに小さい最小DFAがあります。そして、それはサンプルシーケンスを受け入れることができます。

上記の例では、*演算子のみを考慮しています。より一般的には、オペレーター|はDFAサイズを縮小することも考えられます。

したがって、一般的な質問は次のとおりです。

一連のシンボルが与えられた場合、それを受け入れることができる最小のDFAを見つける方法は？

4

2 に答える 2

2

簡単。1つの状態を持つDFAは常にそれを行うことができます。その1つの状態は開始状態であり、状態を受け入れ、すべてのシンボル遷移がループバックします。その些細なDFAはすべての文字列（∑ *）を受け入れ、間違いなく可能な限り最小のDFAです。

于 2012-10-19T03:00:11.903 に答える
2
  1. 正規表現->NFA
  2. 次に、NFA-> DFA
  3. 次にDFA->最小DFA

あなたが各ステップのためにグーグルすることができるオンラインのアルゴリズムの束があります。
また、DFA/NFAを確認できます。
http://hackingoff.com/compilers/regular-expression-to-nfa-dfa

于 2012-10-19T03:59:01.690 に答える