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

Question

非決定論的写像に関する本を読んだところ、 M=(Q,∑,trans,q ₀ ,F) に対してQ*∑ から 2 ^Qへ​​の写像があり、ここで Q は状態の集合です。^{でもどうやって2Q}なのかわからない。a、b、cの3 つの状態がある場合、どのようにして 8 つの状態にマッピングされるのでしょうか?

Answer 1

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

これは、Q = { a、b、c }である実際の例です。この場合、| Q | は3（3つの要素があります）なので、2 ³は8です。つまり、先頭ビットが要素a用、次のビットがb用、末尾ビットがc用であるとすると、これが得られます。

• 0 = 000 = {}
• 1 = 001 = { c }
• 2 = 010 = { b }
• 3 = 011 = { b、c }
• 4 = 100 = { a }
• 5 = 101 = { a、c }
• 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 つの状態 abc がある場合、セット 2 ^Qは 8 つの要素 {{}、{a}、{b}、{c}、{a,b}、{a,c}、{b,c} で構成されます。 、{a、b、c}}。8 つの状態にマップされるのではなく、これら 8 つのセットのいずれかにマップされます。HTH