3

上限は 2^n であり、これらが両方とも有限のマシンであることを考えると、n 状態 NFA と 2^n 以下の状態を持つ DFA の両方の交差が有効になるため、そう考えています。

私はここで間違っていますか？

4

2 に答える 2

1

それは正しいです。ご存知かもしれませんが、DFA と NFA はどちらも通常の言語のみを受け入れます。つまり、受け入れることができる言語は同じです。また、NFA を DFA に変換する最も原始的な方法は、サブセット構築 (パワーセット構築とも呼ばれます)を使用する方法です。この方法では、NFA の状態の組み合わせごとに DFA で状態を作成するだけです。これは状態のパワーセットと呼ばれ、最大でも 2^n です。

しかし、@SasQ が述べたように、これは最悪のシナリオです。通常、Hopcroft のアルゴリズムまたは Brozowski のアルゴリズムを使用すると、それほど多くの状態にはなりません。

于 2011-03-09T06:49:04.367 に答える
1

あなたが正しい。2^n は上限であるため、生成された DFA はその上限を超える状態を持つことはできません。しかし、それは最悪のシナリオです。最も一般的なシナリオでは、結果の DFA よりも状態が少なくなります。場合によっては、元の NFA よりもさらに少なくなる可能性があります。

しかし、私の知る限り、結果の DFA が実際にいくつの状態を持つかを予測するアルゴリズムはまだ存在しません。それで見つけたら教えてください(;_;)

于 2011-03-09T06:24:05.883 に答える