Theoretische Grundlagen der Informatik

at Karlsruher Institut für Technologie

Join course
222
Next exam
AUG 27
Discussion
Documents
Flashcards
Es fehlen hier noch C|B
[HK WS18 bzw. klausur1ws1718] Problem 3 (a) Warum war das hier genug zu zeigen, wenn eine TM L entscheidet, dann entscheidet sie auch Lu, was eig. nicht möglich ist. Kann es nicht immer noch möglich sein, dass Lc semi-entscheidbar ist? Was hat uns die Lösung über die semi-Entscheidbarkeit von Lc gesagt? Danke im Voraus
[NK SS18 bzw. klausur2ws1718] Problem 4 (a) Weiß jemand, woher die beiden Formeln stammen? Ich habe nichts darüber in der VL bzw. Übung gefunden. Wenn man selber darauf kommen sollte, weißt jemand grob wie? Danke im Voraus.
In der Aufgabenstellung steht, dass du im Alphabet mindestens 2 Zeichen hast. Also bei einem Wort der Länge n, gibt es mindestens 2^n Moglichkeiten, wie dieses Wort aussehen kann. Soviel zur ersten Formel. Die zweite kommt daher, dass 2^log(|ΓxQ|) gerade |ΓxQ| ergibt (log zur Basis 2), also hättest du mit log (|ΓxQ|) als Wortlänge genau |ΓxQ| Wörter und es ist möglich, dass jedes Wort eine eigene Essenz hat. Wenn du ein n0, das gößer als log(|ΓxQ|) ist, wählst, hast du mehr mögliche Wörter, nämlich 2^n0 (>2^log(|ΓxQ|)), als mögliche Essenzen und es MUSS zwei Wörter mit der gleichen Essenz geben.