0 Daumen
879 Aufrufe

sei L eine entscheidbare Sprache und k ∈ N. Zeigen Sie, dass dann auch die Sprache L^k := { w | ∃ v₁,...vk ∈ L mit w= v₁,...vk} entscheidbar ist.

Wie kann man so etwas zeigen? Komm hier nicht weiter...

Lg

Avatar von

1 Antwort

+2 Daumen
 
Beste Antwort

Eine Sprache \(L\subseteq \Sigma^*\) ist genau dann entscheidbar, wenn es eine Turingmaschine \(M\) mit den Endzuständen \(1\) und \(0\) gibt, die für jedes Wort \(w \in \Sigma^*\) einen Endzustand erreicht und genau dann den Endzustand \(1\) erreicht, wenn \(w\in L\) ist.

Demnach solltest Du zuerst für \(L\) eine Turing-Maschine entwerfen und diese dann so umbauen, dass sie \(L^k\) entscheidet. Hier noch etwas Lektüre: http://www.informatik.uni-leipzig.de/~brewka/papers/Entscheidbarkeit.pdf

Avatar von

Danke hat mir geholfen!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community