Erklärug der Lösung zu i. und ii.

Question

Könnte mir jemand bitte die Frage i und ii erklären? Warum die Antwort so ist, wie sie ist?

Answer 1

i) Für ein Wort aus einer endlichen Menge von Wörtern kann man sich immer einen Kellerautomaten definieren, der genau dieses Wort erkennt, indem man die Zustände speziell auf dieses eine Wort abstimmt. Da es sich um eine endliche Menge handelt, kann man das theoretisch für jedes Wort aus der Menge so machen. Der enstehende Kellerautomat hat dann sehr viele (aber endlich viele) Zustände und ist nicht-deterministisch.

ii) Es gibt Sprachen, die nicht in L0 liegen und somit auch nicht von einer TM erkannt werden können (siehe dazu Diagramm von Folie 5-31).

Viele Grüße,

Sven (Tutor)