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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

2 Pluspunkte 0 Minuspunkte
292 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!
in Kapitel 3 von  

1 Eine Antwort

2 Pluspunkte 0 Minuspunkte
 
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.)

von Dozent (10.1m Punkte)  
ausgewählt von
0 0
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!
1 0
Vielen Dank für die schnelle und ausführliche Antwort! Mir ist jetzt klar, wo mein Denkfehler lag.
...