Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität 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$.

Kommentiert: Begründungen für die Aussagen

Sun, 16 Nov 2014 16:32:48 +0000

Hi,

es gilt, dass LdetKA(E) Teilmenge von LndetKA(E) ist. Die Beziehung in der anderen Richtung gilt allerdings nicht. Wie in der Vorlesung gezeigt, kann ein nichtdeterministischer KA Sprachen der Form w = uu' (wobei u' das Spiegelbild von u ist) erkennen, das kann ein det KA jedoch nicht. Daher kann die Sprachmächtigkeit nicht gleich sein.
Bei Touringmaschinen ist die Mächtigkeit von det und ndet gleich. Falls du noch Fragen hast, schau dir am besten nochmal die VL-Folien dazu an und sag dann, wo noch Erklärungsbedarf ist.

Gruß,
Jonas (Tutor)