0 Daumen
46 Aufrufe

Beweisen oder widerlegen Sie die folgenden Aussagen


(a) Seien \( L \) und \( L^{\prime} \) entscheidbare Sprachen. Dann ist \( L \cap L^{\prime} \) auch entscheidbar.
"DTM" steht fĂŒr "Deterministische Turing-Maschine".
(b) Wird \( L \) von einer Deterministischen Turing-Maschine \( M \) aufgezÀhlt, dann ist das Komplement von \( L \) akzeptierbar.
(c) Die Vereinigung des Komplements einer entscheidbaren Sprache mit dem Komplement einer aufzÀhlbaren Sprache ist rekursiv.
(d) Zu einer Nichtdeterministischen Turing-Maschine und Eingabewort \( w \) kann es ĂŒberabzĂ€hlbar viele Rechnungen geben (Rechnungen sind unendliche Folgen von Konfigurationen).
(e) Es werde \( L \) durch eine Deterministische Turing-Maschine aufgezÀhlt. Dann gibt es eine Nichtdeterministische Turing-Maschine, die das Komplement akzeptiert.
(f) Jede von einem Pushdown-Automaten (PDA) akzeptierte Sprache wird von einer Deterministischen Turing-Maschine entschieden.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community