FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

Aufg. 10.2

Aufg. 10.2 2006-06-15 16:28
MB
bei dieser aufgabe soll man eine TM angeben, die die Menge
[img]http://mokrates.de/cgi-bin/texstring?%5C(L:=%5C%7Bwcw%7Cw%20%5Cin%20%5C%7Ba,b%5C%7D%5E+%5C%7D%5C)[/img]
akzeptiert.(das c ist eiegtnlich ein vertikal durchgestrichenes c).
jetzt frage ich mich wo da die schwierigkeit liegen soll, denn eine Maschine die diese Menge nur akzeptiert ist doch nicht schwer anzugeben oder?

Re: Aufg. 10.2 2006-06-15 17:13
f0k
Naja, es ist beide Male das selbe w, also es muss vor dem c und hinter dem c genau die gleiche Abfolge aus ahs und behs sein. Ein bisschen nachdenken muss man also schon. Aber er hat ja sogar ungefähr erklärt, wie man das machen könnte. Ich find's 'ne schöne Aufgabe.

Re: Aufg. 10.2 2006-06-15 17:32
MB
ist das c denn eigentlich ein wort oder ein "trenn-symbol", dass angibt, dass m an w halbieren kann und dann 2x das gleiche hat??

Re: Aufg. 10.2 2006-06-15 18:28
UncleOwen
c ist ein Symbol, das im akzeptierten Wort genau in der Mitte vorkommen muss.

Re: Aufg. 10.2 2006-06-15 19:52
tilo
Beim Vergleich der Wörter: Ich hab das jetzt so gemacht, dass ich Buchstaben gelöscht habe und fürs Löschen hab ich einfach ein _ geschrieben. Das ist aber garnicht zulässig, oder?

Re: Aufg. 10.2 2006-06-15 20:22
f0k
Doch, solange Du das _ bei der Definition deiner Maschine ins Bandalphabet aufnimmst, ist das erlaubt. Die Eingabe muss am Ende nicht mehr lesbar sein. Hauptsache, die Maschine bleibt für alle Eingaben aus L in einem Endzustand stehen und für alle anderen Eingaben nicht.

Re: Aufg. 10.2 2006-06-16 03:01
georg
Beim Vergleich der Wörter: Ich hab das jetzt so gemacht, dass ich Buchstaben gelöscht habe und fürs Löschen hab ich einfach ein _ geschrieben. Das ist aber garnicht zulässig, oder?

Was f0k geschrieben hat, ist richtig, aber um das nochmal
explizit zu sagen: das hat natürlich nur zur Folge, dass
das Symbol, das vorher an der Stelle stand, durch _ ersetzt
wird; aus dem Bandinhalt xyz wird also x_z und nicht xz.
Wenn du das beachtest, ist das kein Problem.

Re: Aufg. 10.2 2006-06-16 10:13
tilo
Ja, danke nochmal. Mein Denkansatz war da etwas daneben, kann jetzt garnicht mehr erklären, was ich da gedacht hab ;)

Re: Aufg. 10.2 2006-06-17 20:14
MB
irgendwie pick ich das nicht. das wort steht ja auf einem band und wir haben auch nur das, da es einen 1-band maschine sein soll. aber wie kann ich das wort jetzt "analysieren"? denn man weiss ja auch nicht wie lang es ist, um zB mit dem kopf in die mitte zu gehen und so beide wort-teile zu vergleichen. um es kurz zu sagen: ich stehe mal wieder auf dem schlauch. [img]http://www.fb18.de/gfx/lachen.gif[/img]

Re: Aufg. 10.2 2006-06-17 20:49
Anarch
Ich nehme mal an, dass das c aus der Definition nicht in w sein darf… Damit wird es einfach.

Re: Aufg. 10.2 2006-06-17 21:58
DeGT
Ich nehme mal an, dass das c aus der Definition nicht in w sein darf… Damit wird es einfach.

Das ist ganz klar so, da ja w nur a und b enthält und c ein ganz normales Zeichen ist (also nichts mit a oder b).
Hat Jantzen bei der letzten Vorlesung so weit ich das richtig mitbekommen habe auch gesagt.

Re: Aufg. 10.2 2006-06-17 23:21
tilo
Meine Maschine löst das ganze so, dass sie den ersten Buchstaben anguckt, dann den ersten nach dem c - und das dann so lange mit dem zweiten, dritten, … , bis alle durchlaufen sind.

Re: Aufg. 10.2 2006-06-18 19:40
Anonymer User
meine macht das auch

Aber die frage ist steht das c mit auf dem band also z.b.

aaaabcaaaab ?

oder

aaaabaaaab ?

HILFE !

Re: Aufg. 10.2 2006-06-18 19:42
Anarch
Bei aaaabaaaab – wo ist das c aus der Aufgabenstellung?

Ja, auf dem Band steht aaaabcaaaab …