Formale Sprachen Akzeptanzproblem verstehen

Question

Hallo Leute,

ich habe eine Frage zum Akzeptanzproblem. Das Akzeptanzproblem ist folgendermaßen definiert A = { <M> x | M ist DTM, die die Eingabe x akzeptiert}.

Gibt es eine Eingabe für A, sodass die Eingabe nicht akzeptiert wird?

Answer 1

Willst du wissen, welche Formale Sprach Klassen eine DTM akzeptiert? Das sind die Chomsky Typen 3, 2 und 1. Typ-0-Sprachen werden nur teilweise von DTMs erkannt, man braucht oftmals NTMs.

Wenn du das Halteproblem meinst, dass ist etwas komplizierter. Das erkläre ich dir gerne, falls es das ist, was du wissen möchtest.

Comments

Für mich wäre nur interessant, ob es eine Eingabe für M gibt, sodass M nicht akzeptiert?

---

Ja, das kommt dann darauf an, welche Grammatik für die akzeptierten Wörter der Sprache definiert ist. DTM akzeptiert ja nach einer Grammatik (Chomsky-Typ 1 bis 3) bestimmte Eingaben (x), ob sie zur Grammatik G der Sprache L gehören. Du müsstest also irgendwo noch eine Grammatik haben oder eben das Zustandsdiagramm zur DTM, um zu entscheiden, für welche x die Eingabe nicht akzeptiert wird.

Ganz sicher ist: bestimmte Eingaben werden auf jeden Fall nicht akzeptiert.

---

Aha Ok danke dann macht die Lösung zu meiner Aufgabe Sinn, wenn es eine bestimmte Eingabe gibt die nicht akzeptiert wird.