Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Nichtdet. bei Tuningmaschinen Infobuch S. 102

+2 Punkte
240 Aufrufe
Guten Tag,

zu Beginn von Kapitel 3.1, S. 102 wird die ndetTM eingeführt. Meine Frage richtet sich an die ndet Zustandsübergangsfunktion:

delta(s, b) =  {(s1, b1, X1),..., (sm, bm, Xm)} (= Potenzmenge(S x B  {R, L, N})

 

Warum wird hier Potenzmenge gebildet? Ist es nicht ausreichend das Kartesische Produkt zu bilden? Darin sind doch bereits alle möglichen Tupel enthalten oder täusche ich mich?

 

Vielen Dank im voraus!
Gefragt 12, Nov 2016 in Kapitel 3 von Anonym  

Eine Antwort

+2 Punkte
 
Beste Antwort

Nein, es muss schon die Potenzmenge sein. Ich weiß nicht genau, wie Sie das mit dem kartesischen Produkt meinen (vielleicht können Sie das noch etwas genauer ausführen), aber es geht darum, dass für jeden Übergang eine beliebige Teilmenge aller möglichen Tupel $(s, b, X) \in S \times B \times \{R, L, N\}$ angegeben werden kann (von denen dann eines während der Rechnung nichtdeterministisch ausgewählt wird).

Wenn wir beispielsweise zwei Zustände $S=\{s_1, s_2\}$ und zwei Bandzeichen $B=\{1, \star\}$ haben, dann ergeben sich folgende theoretisch mögliche Tupel für jeden Übergang:
$$S \times B \times \{R, L, N\} =
\begin{array}{l}
\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L), (s_2, \star, L),  \\
(s_1, 1, R), (s_2, 1, R),(s_1, \star, R),(s_2, \star, R),  \\
(s_1, 1, N), (s_2, 1, N),(s_1, \star, N),(s_2, \star, N)\}
\end{array}$$
Nun kann jede belibige Teilmenge dieser Menge für einen Übergang genommen werden. Das könnte beispielsweise $\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L)\}$ sein oder $\{(s_1, 1, L), (s_1, 1, N), (s_2, \star, R)\}$ oder auch einfach die leere Menge $\emptyset$.

Die Menge all dieser Teilmengen, aus denen für die Definition des Übergangs ausgewählt werden darf (durch Sie als Ersteller der Turingmaschine), ist aber gerade die Potenzmenge:
$$\wp(S \times B \times \{R, L, N\})$$

Der nichtdeterministische Rechenprozess wählt dann während der Rechnung aus der Menge, die Sie für den Übergang definiert haben, ein einzelnes Tupel aus, mit dem weitergerechnet wird. (Etwa aus der Menge $\{(s_1, 1, L), (s_2, 1, L), (s_1, \star, L)\}$ das Tupel $(s_1, \star, L)$ oder so...)

(Das kartesische Produkt der Menge $S \times B \times \{R, L, N\}$ mit sich selbst, also $(S \times B \times \{R, L, N\})\times(S \times B \times \{R, L, N\})$, würde ja lauter Paare $\left(\left(s_1, 1, L\right), \left(s_1, 1, L\right)\right)$ usw. enthalten, das ist hier nicht hilfreich.)

Beantwortet 12, Nov 2016 von Lukas König Dozent (10,065,100 Punkte)  
ausgewählt 12, Nov 2016 von Lukas König
Ich hoffe, dass es damit klarer wird. Dieser Teil ist natürlich für das intuitive Verständnis eine der größten Herausforderungen der theoretischen Informatik. Zögern Sie nicht sich zu melden, wenn es weiterhin Schwierigkeiten gibt!
Vielen Dank für die schnelle und ausführliche Antwort! Mir ist jetzt klar, wo mein Denkfehler lag.
...