Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

0 Punkte
66 Aufrufe
Könnte mir jemand bitte die Frage i und ii erklären? Warum die Antwort so ist, wie sie ist?
Gefragt 22, Okt 2014 in SPR-AD von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...