Zeigen Sie, dass die Sprache L^k := { w | ∃ v₁,...vk ∈ L mit w= v₁,...vk} entscheidbar ist.

Question

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

Answer 1

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

Comments

Danke hat mir geholfen!