infostudium.de

von **loiseau** » 12.12.07 12:41

Hallo zusammen.

Wir haben uns mal den Fragenkatalog vorgenommen und ein Blatt mit Antworten erstellt.

Wenn Bedarf besteht schaut einfach mal drauf ;-)

Falls ihr Fehler / Unzulänglichkeiten findet, würden wir uns über ernst gemeinte Rückmeldungen freuen.

Das Dokument findet ihr hier: http://fightermv.fi.funpic.de/fragen-antworten.pdf

von **mirko** » 12.12.07 12:58

loiseau hat geschrieben:Falls ihr Fehler / Unzulänglichkeiten findet, würden wir uns über ernst gemeinte Rückmeldungen freuen.

dann fang ich gleich mal an

:

1. der 7-tupel einer TM _beginnt_ mit der zustandsmenge Q
2. eine nachfolgekonfiguration kann in beliebig vielen schritten folgen - die _direkte_ nachfolgekonfiguration folgt in einem einzigen schritt

von **mgla** » 13.12.07 09:58

4 ist nicht formal definiert. Darum gehts in der Frage.
$M = $Q,\Sigma, \Gamma, B, q_0,q_{ende}, \delta$\\ mit \\ Q = \{q_0, q_1,q_{ende}\}\\ \Sigma = \{0,1\}\\ \Gamma = \Sigma \cup \{B\}\\ \delta =$

Code: Alles auswählen: 0 1 B q0 (q0,0,R) (q1,1,R) accept q1 reject (q1,1,R) accept

von **mirko** » 13.12.07 10:16

mgla hat geschrieben:4 ist nicht formal definiert. Darum gehts in der Frage.
$M = \{Q,\Sigma, \Gamma, B, q_0,q_{ende}, \delta\}\\ mit \\ Q = \{q_0, q_1,q_{ende}\}\\ \Sigma = \{0,1\}\\ \Gamma = \Sigma \cup \{B\}\\ \delta =$
Code: Alles auswählen
0 1 B q0 (q0,0,R) (q1,1,R) reject q1 reject (q1,1,R) accept

wo du gerade bei formalismen bist:
eine tm ist keine menge, sondern ein tupel

von **mgla** » 13.12.07 10:46

meine mengen sind alle eindeutig geordnet

Aufgabe 8:

Die Register 3,4,5,... enthalten den Inhalt der Speicherstellen 0,1,2,3.... .

Hier müsste es heißen: Die Register 3,4,5.. enthalten den Inhalt der bereits vom Kopf besuchten oder am Anfang auf dem Band stehenden (=/= B)Speicherzellen.

von **pfeiffenaugust** » 13.12.07 11:04

moin,

ist die antwort bei 23b) so richtig?
bei der vereinigung mehrer rek. aufzählbarer TM muss die simulation doch parallel erfolgen.
wenn man einfach M1,...Mi nacheinander simuliert - so könnte es ja passieren - das is sich eine TM in einer endlosschleife "hängt".
s. satz 1.32b)

von **mirko** » 13.12.07 11:29

pfeiffenaugust hat geschrieben:moin,

ist die antwort bei 23b) so richtig?
bei der vereinigung mehrer rek. aufzählbarer TM muss die simulation doch parallel erfolgen.
wenn man einfach M1,...Mi nacheinander simuliert - so könnte es ja passieren - das is sich eine TM in einer endlosschleife "hängt".
s. satz 1.32b)

denke ich auch - wobei man "parallel" dann vlt noch genauer spezifizieren sollte - wir haben schließlich keine n-core-tm

also quasi: simuliere c schritte von M1, dann c schritte von M2, ..., dann c schritte von Mn, dann wieder c schritte von M1, usw bis die erste tm angehalten hat - wenn diese verwirft nimm sie aus der kette raus und führe nur noch die anderen aus - wenn sie akzeptiert, brich ab und gib true aus

von **mgla** » 13.12.07 11:29

In 13. wird nur die Syntax beschrieben, nicht aber die Semantik:

$x_i = x_j + c$
Weist x_i den Wert (x_j + c) zu.
$P_1; P_2$
führt erst P_1 und dann P_2 aus.

WHILE $x_i \neq 0$ DO P END\

Führt so lange P aus, bis x_i = 0 ist.

von **mirko** » 13.12.07 11:32

bei der syntax der loop-schleife sollte man auch noch erwähnen, dass x_i nicht in P_1 vorkommen darf...

von **Fighter_MV** » 13.12.07 12:32

mgla hat geschrieben:4 ist nicht formal definiert. Darum gehts in der Frage.
$M = $Q,\Sigma, \Gamma, B, q_0,q_{ende}, \delta$\\ mit \\ Q = \{q_0, q_1,q_{ende}\}\\ \Sigma = \{0,1\}\\ \Gamma = \Sigma \cup \{B\}\\ \delta =$
Code: Alles auswählen
0 1 B q0 (q0,0,R) (q1,1,R) reject q1 reject (q1,1,R) accept

Darf er verwerfen wenn wir in Zustand q0 sind und dann ein Blank kommt? Ich denke da müsste ein accept hin, da Keine Null bzw keine Eins ja zugelassen ist oder?

von **loiseau** » 13.12.07 14:00

Es gibt jetzt eine aktualisierte Version unter der obigen URL.

Die Korrektur von Antwort 8 steht noch aus und kommt heute Nachmittag. Die RAM merkt sich erstmal nur diejenigen Register, die von Anfang an auf dem Band stehen oder während der Simulation benutzt/erzeugt werden.

von **mgla** » 13.12.07 15:42

Fighter_MV hat geschrieben:
Darf er verwerfen wenn wir in Zustand q0 sind und dann ein Blank kommt? Ich denke da müsste ein accept hin, da Keine Null bzw keine Eins ja zugelassen ist oder?

Stimmt, habs geändert. Mich hatte das $\leq$ von anfang an irritiert.

von **Quinie** » 13.12.07 16:15

Mal ganz ehrlich das Frage und Antwortspiel aus dem Kathalog war ja relativ einfach, aber bei den Übungsaufgaben verzweifel ich.

von **mgla** » 13.12.07 16:57

17. Würde ich ruhig alles reinschreiben was es dazu zu wissen gibt:

TM erkennt L, wenn TM auf $w \in L$ hält und akzeptiert, auf allen $w \notin L$ nicht akzeptiert.
L ist semi-entscheidbar und rekursiv aufzählbar.

TM entscheidet L, wenn TM auf für alle w hält, wenn $w \in L$ akzeptiert und $w \notin L$ verwirft.
L ist rekursiv und entscheidbar.

Teilweise redundant, aber das eine entscheidende TM immer hält steht nicht im Antwortkatalog.

von **mirko** » 13.12.07 19:29

mgla hat geschrieben:aber das eine entscheidende TM immer hält steht nicht im Antwortkatalog.

wieso? da steht doch w€L => M akz, w!€L => M verwirft - das impliziert doch M hält für alle w...

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[BuK] Antwortenkatalog zum Fragenkatalog

Antwortenkatalog zum Fragenkatalog

Re: Antwortenkatalog zum Fragenkatalog