Informatiker Board | Druckvorschau: Turingmaschine (Wörter in der Mitte teilen)

Geschrieben von Melissa-1 am 24.01.2013 um 10:25:

Turingmaschine (Wörter in der Mitte teilen)

Meine Frage:
1.
Ich soll eine Turingmaschine mit maximal 12 Zuständen angeben, die in die Mitte eines Wortes das Zeichen | einfügt.
[latex]w = w_1 * w_2[/latex]

[latex]| w_1 | = | w_2 | = | w | /2[/latex]

Zwischen

und

soll nun das Zeichen | eingefügt werden.
Ich muss nur Wörter mit gerader Länge betrachten, was bei Wörtern ungerader Länge passiert ist egal.

2.
Ich soll eine Turingmaschine beschreiben (in eigenen Wörtern), die bei Wörtern der Sprache L in akzeptierenden Zuständen hält.

$[latex]L=\left\{ w\in \left\{ a,b\right\}^{+} | \exists u \in \left\{ a,b\right\}^{*}: www= uu \right\} [/latex]$

Meine Ideen:
Mealy-Automaten, Moore-Automaten und endliche Akzeptoren hab ich super verstanden, aber bei Turingmaschinen komm ich nicht zu Recht.

2.
Erst einmal überlege ich mir welche Wörter in der Sprache liegen.
(aa)*
(bb)*
(abab)*
(baba)*

An sich müsste die Turingmaschine ähnlich funktionieren wie die erste.
Sie schreibt das Wort 3* hintereinander auf teilt es in der Mitte und vergleicht ob die beiden neuen Wörter identisch sind.

Ich hab leider keine Ahnung wie ich vorgehen soll. Kann mir jemand helfen?

Geschrieben von Karlito am 24.01.2013 um 21:37:

Hallo,

ich würde eine Zeiband-TM verwenden. Für Aufgabe 1 würde ich das 2. Band zum Zählen verwenden. Das kannst du machen, indem du vom Eingabeband immer 2 Zeichen liest und eines auf das zweite Band schreibst.

Hilft das als Tipp? Beschreibe mal die Zustände, welche du Brauchst und was du darin tust. Sollte das nicht schon reichen, würde ich dir den "Zählvorgang" mal beschreiben und danach sehen wir weiter...

VG,

Karlito