Deterministischen / nicht-deterministisches Zustandssystem-Mapping

Question

ich in einem Buch gelesen auf nicht-deterministische Abbildung ist Abbildung von Q * S bis 2 ^Q für M = (Q, S, trans, q ₀ , F) wobei Q eine Menge von Zuständen. Aber ich bin nicht in der Lage zu verstehen, wie es ist 2 ^Q ; wenn es 3 Zustände a b c , wie es zu 8-Staaten abbildet?

Answer 1

Ich fand immer, dass der einfachste Weg, um diese zu denken (da der Satz von Zuständen endlich ist) ist als jede dieser Untergruppen, die seine eine Codierung einer Basis-2-Zahl, die im Bereich von 0 (alle Bits Null) bis 2 ^{| Q |} -1 (alle Bits eins), wo es so viele Bits in der Zahl sind, wie es Mitglieder in den Zustand versetzt, dann Q., können Sie nehmen nur eine dieser Zahlen und Karte sie in eine Untergruppe unter Verwendung, ob ein bestimmtes Bit in der Zahl festgelegt ist. Easy!

Hier ist ein ausgearbeitetes Beispiel, wo Q = { a , b , c }. In diesem Fall | Q | 3 ist (es gibt drei Elemente) und so 2 ³ ist 8. Das bedeutet, dass wir das, wenn wir sagen, dass das führende Bit für Elemente a , das nächste Bit ist für b , und die Hinter Bit für 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 }

Sehen Sie? Dass die ersten drei Zustände hat in 8 umgewandelt worden, und wir haben eine natürliche Nummerierung von ihnen, dass wir die Etiketten dieser Staaten zu schaffen nutzen könnten, wenn wir gewählt haben.

Nun zu den Interpretationen dieses in einem nicht-deterministischen Kontext. Grundsätzlich sind die Nicht-Determinismus bedeutet, dass wir nicht genau wissen, was Zustand wir sind in. Wir vertreten diese durch einen Pseudostaat mit, dass der Satz von „echten“ Staaten ist, dass wir könnte werden in ; wenn wir insgesamt nicht-Determinismus haben, dann sind wir in dem pseudo-Zustand, in dem alle wirklichen Staaten möglich sind (dh { a, b, c }), während der pseudo-Zustand, in dem keine wirklichen Staaten sind möglich (dh {}) ist das gegenteil (und soll unmöglich sein, um wirklich im Übergangssystem zu erreichen). In einem realen System, sind Sie in der Regel nicht mit einem von diesen beiden Extremen zu tun.

Die Logik, wie Sie das deterministische Übergangssystem in eine nicht-determinis konvertieren ist etwas komplexer, als ich in hier gehen will. (Ich hatte eine wesentliche Doktorarbeit zu lesen, es zu lernen, so ist es auf jeden Fall mehr als eine SO Antwort wert!)

Answer 2

2 ^Q Mittel, um die Menge aller Teilmengen von Q. Für jeden Zustand q und jeden Buchstaben x von Sigma, gibt es eine Teilmenge von Q heißt es, auf die Sie von q mit dem Buchstaben x gehen können. Also ja, wenn es drei Zustände abc der Satz 2 ^Q besteht aus 8 Elementen {{}, {a}, {b}, {c}, {a, b}, {a, c }, {b, c}, {a, b, c}}. Es ist keine 8-Staaten, es Karten zu einem dieser 8 Sätzen. HTH