Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Turingmaschine

Turingmaschine

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

guguli aktiv_icon

14:54 Uhr, 16.10.2010

Hallo zusammen,
ich habe forlgende fragestellung (sieh Bild) und ehrlich gesagt ich verstehe sie erst gar nicht, kann mir einer Pls helfen diese aufgabe zu lösen?!

THx

teppich aktiv_icon

15:55 Uhr, 16.10.2010

Wo tauchen denn die Probleme auf? Bei der Definition einer Turingmaschine, beim binären Rechnen oder beim Aufstellen der Überführungsfunktion?

guguli aktiv_icon

16:08 Uhr, 16.10.2010

Also alles ist für mich irgendwie total unverständlich. hab den skript schon paar mal durchgelesen kann aber diese aufgabe trotzdem net lösen.
es wär nett wenn du mir schritt für schritt erklären würdest was da zutun ist. ich weiss das ist viel arbeit :-)...
THX

teppich aktiv_icon

16:42 Uhr, 16.10.2010

Es ist kaum Arbeit, eher der Formalismus ist etwas schwieriger. Es gibt reichlich leicht unterschiedliche Definitionen einer Turingmaschine, deswegen verzichte ich hier darauf, eine anzugeben. Ich beschränke mich auf die

δ

-Funktion, die letztendlich den Algorithmus abarbeitet.

(a) Der Algorithmus ist denkbar einfach:
1. starte ganz links
2. solange kein "blank"-Symbol gelesen wird: invertiere das aktuelle Bit und gehe nach rechts
3. wird ein "blank"-Symbol gelesen sind wir fertig
(oft muss vorher noch getestet werden, ob die Eingabe im korrekten Format vorliegt)

Deine Anfangssituation bei

w = 11001

ist:

\begin{array}{rcl} # & 1 & 1 & 0 & 0 & 1 & # \\ ↑ \end{array}

Zustand:

q_{0}

Wir berechnen also

δ (q_{0}, 1) = (q_{0}, 0, R)

, denn statt der gelesenen

1

schreiben wir eine

0

aufs Band, bleiben im gleichen Zustand und gehen ein Feld nach rechts.
Nach einem Schritt ist die Situation die folgende:

\begin{array}{rcl} # & 0 & 1 & 0 & 0 & 1 & # \\ ↑ \end{array}

Zustand:

q_{0}

Ich hoffe das Prinzip ist deutlich geworden. Der Kern bei solchen Aufgaben ist, einen Algorithmus zu finden, der die umzusetzende Berechnung durchführt. Hier hat

δ

nur drei Eingabefälle:

δ (q_{0}, 0) = (q_{0}, 1, R)

"im Zustand

q_{0}

eine 1 gelesen

\to

bleibe in

q_{0}

, schreibe eine 0 und gehe nach rechts"

δ (q_{0}, 1) =

δ (q_{0}, #) =

(b) Hinweis: Um eine Binärzahl mit 16 zu multiplizieren, muss man nur vier Nullen anhängen.

guguli aktiv_icon

18:58 Uhr, 16.10.2010

δ (q_{0}

) = (F,0, N)

F =

endzustand
das soll heissen

p_{0}

kann kein # lesen denn sonst das Wort würde da enden nud somit ist es nicht in der Sprache enthalten????

teppich aktiv_icon

19:05 Uhr, 16.10.2010

Fast richtig, sobald die Maschine ein

#

liest, sind wir fertig. Bei dir wird in diesem Fall jedoch das erste

#

mit einer

0

überschrieben, womit bei dir "

w ʹ

und eine zuätzliche

0

" auf dem Band stünden.
Wählst du statt dessen

δ (q_{0}, #) = (F, #, N)

, so steht nur

w ʹ

auf dem Band.

guguli aktiv_icon

19:41 Uhr, 16.10.2010

also ich find es ist besser dass ich dir erstmal schreibe wie ich tm überhaupt lese so kannste mich wahrscheinlich besser korrigieren :-) also siehe Bild erst mal

δ (q_{0}, 0) = (q_{0}, 0, R)

im zustand

q_{0}

wird eine 0 gelesen, bleibt in

q_{0},

schreibt eine 0 und geht nach rechts weiter

δ (q_{0}, 1) = (q_{0}, 1, R)

im zustand

q_{0}

wird eine 1 gelesen geht zu

q_{1}

über und nach rechts weiter

δ (q_{0}, B) = (q, B, N) q_{0}

kann nihct zu Endzustand über

\Rightarrow

die Sorache enthält mindestens eine 1.

δ (q_{1}, 0) = (q_{1}, 0, R)

im zustand

q_{1}

wird eine 0 gelesen bleibt in

q_{1},

schreibt eine 0 und geht nach rechts weiter

δ (q_{1}, 1) = (q_{1}, 1,

R)im zustand

q_{1}

wird eine 1 gelesen bleib in

q_{1}

und schreibt eine 1 und nach rechts weiter

δ (q_{1}, B) = (q_{2}, B, L)

Hier wird ein

B

gelesen(ende des wortes) geht über zu

q_{2}

schreibt einB und geht nach links

δ (q_{2}, 0) = (q_{2}, 1, L)

im zustand

q_{2}

eine 1 gelesen bleibt in

q_{2},

schreibt eine 0 und geht weiter nach links

δ (q_{2}, 1) = (q_{3}, 0,

L)im zustand

q_{2}

wird eine 0 gelesengeht zu

q_{3}

über und schreibt eine 0 dann geht weiter nach Links

δ (q_{2}, B) = (q, 0, N) q_{2}

kann net zu Endzustand übergehen, denn das wort ist nihct in der sprache enthalten.

δ (q_{3,0}) = (q_{3},

0,L)im zustand

q_{3}

wird eine 0 gelesen bleibt in

q_{3}

und schreibt eine 0 dann geht weiter nach links

δ (q_{3}, 1) = (q_{3}, 1, L)

im zustand

q_{3}

wird eine 1 gelesen bleibt in

q_{3},

schreibt eine 1 und geht nach links weiter

δ (q_{3}, B) = (q, B,

R)im zustand

q_{3}

wird ein

B

gelesen , wir befinden uns am Anfang des Wortes und gehen wir weiter nach Rechts.

also meiner Meinung nach beschreibt diese TM eine Funktion:

{0^{n} 1^{m} 0^{b} 1^{a} | n, b, a \geq 0, m \geq 1}

teppich aktiv_icon

20:20 Uhr, 16.10.2010

Soweit ich das sehe, prüft die TM, ob die Eingabe eine

1

enthält und invertiert dann binär:

in

q_{0}

: laufe nach rechts bis zur ersten

1

von links und wechsle in

q_{1}

; Ende, falls vorher # gelesen
in

q_{1}

: laufe nach rechts bis zum ersten #, wechsle in

q_{2}

q_{2}

: laufe nach links bis zur ersten

1

und invertiere alle Zeichen binär, wechsle in

q_{2}

; Ende, falls # gelesen
in

q_{3}

: laufe nach links bis zum ersten # und invertiere alle Zeichen binär, wechsle in Endzustand

guguli aktiv_icon

20:37 Uhr, 16.10.2010

ist dann die Sprache die ich geschrieben habe denn richtig????

guguli aktiv_icon

11:15 Uhr, 18.10.2010

hey,
sicher, dass in

q_{2}

invertiert wird??? und falls ja wie kann denn die Funktion aussehen????

mfG

teppich aktiv_icon

18:05 Uhr, 18.10.2010

Wenn die TM im Zustand

q_{2}

ist und eine

0

liest, schreibt sie eine

1

zurück. Wird eine

1

gelesen, kommt eine

0

zurück aufs Band und die TM wechselt in den Zustand

q_{3}

.

Seien

Σ = {0, 1}^{}

das Eingabealphabet und

w \in Σ^{*}

ein Eingabewort.
Enthält

w

eine

1

, dann steht am Ende auf dem Band

w ʹ

(das bitweise Komplement);
enthält

w

keine

1

, dann steht am Ende auf dem Band

w ʹ = w

(unverändertes Eingabewort).

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

805590

804720

	Status: nicht eingeloggt	Noch nicht registriert?