GBI Tutorium 13

Die Zustandsmenge, das Bandalphabet und das zugehörige Band (Eingabe- und Rechenband) einer Turingmaschine sind endlich

• falsch

• wahr

Wann akzeptiert ein Turingmaschinenakzeptor akzeptiert ein Wort w?

• Wenn er beim Durchlaufen des Wortes ausschließlich akzeptierende Zustände durchläuft

• Wenn er nach Lesen von w in einem akzeptierenden Endzustand stoppt

• Genau dann, wenn er auf der Eingabe w stoppt.

• Wenn jeder Zustandsübergang definiert ist.

Die Bewegungsfunktion der Turingmaschine muss nicht unbedingt für jeden Zustand und jedes Zeichen definiert sein.

• falsch

• wahr

Wenn für eine Eingabe w eine Turing-Maschine T eine Konfiguration erreicht, sodass die Position des
Kopfes von T in allen Nachfolgekonfigurationen unverändert bleibt, dann hält T für w an.

• wahr

• falsch

Wenn für eine Eingabe w eine Turing-Maschine T eine Konfiguration erreicht, sodass die Beschriftung des
Bandes in allen Nachfolgekonfigurationen unverändert bleibt, dann hält T für w an.

• wahr

• falsch

Wenn für die Turing-Maschine T mit Anfangszustand q₀ und Zustandsüberführungsfunktion f der
Übergang f (q₀, □) undefiniert ist, dann muss T bei Eingabe ε anhalten.

• wahr

• falsch

Welche Eigenschaften hat eine Äquivalenzrelation? (Mehrfachnennung)

• reflexiv

• antisymmetrisch

• transitiv

• surjektiv