11

まず、これは NFA を DFA に変換するアルゴリズムを求める質問ではありません。

ほとんどの場合、NFA とほぼ同じ数の状態を持つことになりますが、NFA と同等の DFA には最大で 2 n 個の状態があることが知られています (そして証明されています)。

NFA と同等の DFA が持つ状態数の推定値を予測するにはどうすればよいですか? 2 n 個の状態を持つ同等の DFA を必要とする NFA の特定のタイプはどれですか?

これを尋ねる私の理由は、最小化を考慮せずに、2 n - 1 状態と「死んだ状態」を確実に生成するいくつかの NFA を「発明」できるようにするためです。

4

4 に答える 4

4

あなたの質問の鍵となる非決定論のために、州の数は爆発的に増加します。

各遷移が一意に決定されるNFA、つまり決定性NFAを使用する場合、それは通常のDFAに他なりません。ただし、2つの遷移が可能な状態になると、DFAとは異なります。

変換アルゴリズムを検討し、状態に同じラベルを持つ2つ以上の遷移がある場合に何が起こるかを調べます。これは、状態のセットに対応する新しい状態が必要な場所です。

したがって、問題は、これらのスーパーセット状態のうち実際に到達可能な状態をいくつ見つけるかということになります。もちろん、そのための凝ったアルゴリズムを発明することもできますが、正しい数を取得するには、通常の変換アルゴリズムを実行して、到達不能な状態を削除するだけです。

同等のDFAが2^n個の状態を持つn個の状態を持つNFAについては、非決定性を利用することを検討してください。最初のアイデアは、すべてのトランジションに同じラベルを付けることですが、それはあまりうまくいきません。代わりに、それぞれにいくつかのラベルが付いた状態のすべてのサブセットに何らかの方法で到達できる必要があることを忘れないでください。

開始状態をカウントしない場合は、次の構成を行うことができます。n個のノードを作成し、2 ^ nからの各セットに対して一意のラベルを作成し、NFAでこのラベルを使用してそのセットの各ノードにトランジションを追加します。これにより、n + 1状態（1が開始状態）のNFAが得られ、DFAには2 ^n+1状態が必要です。もちろん、最小化後に2 ^ nのDFA状態が必要になると、さらに注意が必要になります。

于 2010-01-07T16:52:33.040 に答える
2

わかりました、n -> n という仮定から始めましょう。ここで、ある状態から別の x 個の状態に至る非決定論的遷移ごとに、推定値を x 倍します。二重にカウントする可能性があるため、これは正確ではない場合があります。しかし、それはあなたに上限を与えるべきです。

ただし、対応するDFAを構築してから州をカウントする唯一の確実な方法です（私は思います）。

最後に、おそらくいくつかの DFA (およびその点については NFA) を単純化できますが、これはまったく新しい話です ...

于 2010-01-07T16:41:30.010 に答える
0

Jonathan Graehl の優れた回答をさらに拡張します。

というラベルの付いた自己ループの各状態0, 1, ..., Nに追加します。つまり、次の遷移を追加します。A(N)c
0 c-> 0
1 c-> 1
...
N c-> N

次に、起動しないと仮定すると、DFA には Jonathan の DFAcと同じ状態が含まれます。ただし、が状態から観測される2^(N+1)たびに、状態に到達します。したがって、空集合と DFA has states while has states を除いて、のすべてのサブセットが可能です。c{S,j,k,...,z} <> {S}{j,k,...,z}{S,0,...,N}2^(N+2)-1A(N)N+2

于 2015-04-23T12:07:06.157 に答える
0

N の関数として、開始状態 S と最終状態 N を使用すると、この NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

[ab]*これは、最後から N 番目の文字が であるすべての文字列を受け入れることは明らかですa。

の決定化では、以前の N-1 文字を効果的に記憶する必要があります (文字列が予期せず終了したときに、 N 文字前にあったかどうかを判断できるように、A(N)ウィンドウ内の であったすべての位置を知る必要があります)。aa

これがあなたが望んでいた状態の数と正確に一致するかどうかはわかりませんが、少なくとも 2 倍以内です - のすべてのサブセット{0,...,N}が可能ですが、常にS. 2^(N+1)これは状態であるべきですが、状態がありA(N)ましたN+2。

于 2011-10-17T20:55:26.120 に答える