決定論的/非決定論的状態システムマッピング

Question

非決定的マッピングに関する本を読んで、q*∑から2へのマッピングがあります^Q m =（q、∑、trans、q₀、f）ここで、qは一連の状態です。しかし、私はそれがどのようにあるかを理解することができません2^Q; 3つの状態がある場合 a, b, c, 、8つの州にどのようにマッピングされますか？

Answer 1

これらについて考える最も簡単な方法（状態のセットは有限であるため）は、これらのサブセットのそれぞれが0（すべてのビットゼロ）から2の範囲のベース2番号のエンコードであることであることを常に発見しました。^{| Q |}-1（すべてのビット1）、状態セットにメンバーがいるのと同じくらい多くのビットがありますQ。次に、これらの数字のいずれかを取得して、特定のビットかどうかを使用してサブセットにマップすることができます数字が設定されています。簡単！

これがq = {{a,b,c}。この場合、| q | 3（3つの要素があります）、そのため2³ 8.それは、先頭のビットが要素のためであると言うなら、これを得ることを意味します a, 、次のビットはのためです b, 、そして後続のビット c:

• 0 = 000 = {}
• 1 = 001 = {c}
• 2 = 010 = {b}
• 3 = 011 = {紀元前}
• 4 = 100 = {a}
• 5 = 101 = {交流}
• 6 = 110 = {A、b}
• 7 = 111 = {A、B、c}

見る？最初の3つの状態が8に変換されており、選択した場合にそれらの状態のラベルを作成するために使用できる自然な番号があります。

さて、非決定的な文脈の中でこれの解釈に。基本的に、非決定的主義は、私たちがどのような状態にいるかについて不確かであることを意味します。私たちはこれを表しています。 そうかもしれない 入る;完全な非決定論がある場合、私たちはすべての実際の状態が可能な擬似状態にいます（つまり、{A、B、c}）一方、実際の状態が不可能な擬似状態（すなわち、{}）はコンバースです（そして、実際には遷移システムで到達することは不可能であるべきです）。実際のシステムでは、あなたは通常、それらの極端などちらにも対処していません。

決定論的遷移システムを非決定論的システムに変換する方法の論理は、ここに行きたいよりもかなり複雑です。 （私はそれを学ぶためにかなりの博士論文を読まなければならなかったので、それは間違いなくSOの答えの価値以上です！）

Answer 2

2^Q Qのすべてのサブセットのセットを意味します。各状態QとSigmaの各文字Xについて、Q状態のサブセットが文字XでQから行くことができます。ええ、3つの状態がある場合は、セット2^Q 8つの要素{{}、{a}、{b}、{c}、{a、b}、{a、c}、{b、c}、{a、b、c}}で構成されています。 8つの州にマッピングされず、これらの8つのセットのいずれかにマッピングします。 Hth