Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in SPR-AC

Beantwortet: Jede Sprache ist Teilmenge einer regulären Sprache

Mon, 02 Feb 2015 19:02:33 +0000

Unter 1.) habe Sie das genau richtig beschrieben.

Unter 2.) haben Sie den Fehler gemacht, Sprachen und Sprachklassen durcheinanderzuwerfen. Es gibt durchaus Sprachen, die nicht Element der (Menge der) regulären Sprachen sind. Oder anders gesagt, bspw. ist die Menge der kontextfreien Sprachen nicht Teilmenge der Menge der regulären Sprachen. Aber trotzdem ist jede Sprache Teilmenge einer regulären Sprache, nämlich gilt bspw. für jede beliebige Sprache $L$: $L \subseteq E^\star$.

Beantwortet: Begründungen für die Aussagen

Sun, 16 Nov 2014 16:30:39 +0000

Deine Begründungen sehen meiner Ansicht nach gut aus :)

Zu 3) ja genau, es steht da LdetKA(E) ist Teilmenge von LndetKA(E). Also sind die beiden Sprachklassen nicht gleich.

Zu 7) Die Sprachmächtigkeit von LndetTM und LTM ist gleich. Auf den Vorlesungsfolien ist dazu eine Beweisidee gegeben. Eine det. TM erreicht auch die Endkonfiguration der ndet TM, aber im schlechtesten Fall mit exponentiell höherer Laufzeit!

Viele Grüße

Christiane(Tutorin)