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

Schöne Ferien!
 

 

Wann erkennt Turingmaschine ein Wort ?

–1 Punkt
72 Aufrufe
Hallo,

ich habe in der Vorlesung leider nicht ganz verstanden, wann eine Turing-Maschine ein Wort akzeptiert. Könnte das bitte jemand nochmal erklären?

Vielen Dank!
Gefragt 26, Nov 2014 in TUR-AG von uafjv uafjv Tutor(in) (167,990 Punkte)  

2 Antworten

0 Punkte

Hallo, 

(v1, s, v2) ist eine (akzeptierende) Endkonfiguration falls der Zustand s ein Endzustand ist und keine weitere Folgekonfiguration für (v1, s, v2) existiert.

Das heisst, wenn du einen Übergang mit einem Endzustand hast und du keinen weiteren Übergang findest, mit dem du weitermachen kannst, dann hat die Turingmaschine das Wort akzeptiert.

Noch henauer gesagt. Die Turingmaschine akzeptiert das Wort, wenn du ausgehen von deiner Anfangskonfiguration in (v1, s, v2 ) gelangst.

Ich hoffe das ich dir damit weiterhelfen konnte.

Grüße,

Jördis (Tutorin )

 

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
0 Punkte

Hallo,

Eine Turingmaschine hält akzeptierend, falls sie in einem Endzustand ist und kein weiterer Übergang möglich ist. Sie ist also in einer akzeptierenden Endkonfiguration (v, s, w) mit v ist Bandinschrift links und w ist Bandinschrift rechts vom Schreib-Lese-Kopf und "s ist Element der Menge der Endzustände" und für (v, s, w) existiert keine Folgekonfiguration.

Viele Grüße

Christiane (Tutorin)

 

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...