0 Daumen
60 Aufrufe

Zeigen Sie, dass die folgenden Sprachen unentscheidbar sind.
(a)
\( L_{1}=\left\{n \mid M_{n} \text { akzeptiert unendlich viele Eingaben }\right\} . \)

Benutzen Sie hierzu das allgemeine Halteproblem zur Reduktion.
(b) Sei das zugrundegelegte Bandalphabet \( \Sigma=\{A, a, B, b, C, c, \ldots, Z, z, 3,-\} \).
\( L_{2}=\left\{n \mid M_{n} \text { terminiert nur auf I-love-Inf3, sonst nie }\right\} . \)

Finden Sie eine geeignete Sprache zur Reduktion.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community