D120.de/forum

Hallo zusammen,
ich habe eine Frage: Ist jede Sprache mit endlichem Komplement ist regulär?

Also ich hätte gesagt nein mit der Begründung: Wenn eine Sprache endlich ist dann wird sie von einer (D)TM erkannt also handelt es sich mindestens um eine Sprache mit einer Grammatik (Typ 0). Jedoch ist das Komplement einer Typ0 Sprache nicht entscheidbar. Prinzipiell ist das Komplement einer Typ 0 Grammatik noch nicht mal aufzählbar.

Ist meine Argumentation richtig?

Viele Grüße Patrick

Endliche Sprachen sind AFAIK immer regulär, womit auch ihr Komplement regulär ist.

nicolas hat Recht. Endliche Sprachen sind regulär, und damit auch ihre Komplemente (warum?). Zur Aussage "Das Komplement einer Typ-0-Sprache ist nicht entscheidbar" - im Allgemeinen nicht, aber es gibt auch genügend Typ-0-Sprachen mit entscheidbarem Komplement. Im Allgemeinem ist das Komplement von Typ-0-Sprachen also auch nicht unentscheidbar.

O.K. super vielen Dank! Das heißt müsste aber heißen, das Typ2 (kontextfrei) oder Typ1 (kontextsensitive) oder Typ0 (Allgemein) die nicht endlich sind (also nicht regulär) auch kein endliches Komlement haben?

Viele Grüße Patrick

Ich verstehe Deine Frage nicht. So wie sie da steht ergibt sie keinen Sinn. Nicht endliche Sprachen können natürlich ein endliches Komplement haben, und reguläre Sprachen können auch unendlich sein. Sie haben bloß endlichen Index.

O.K. jetzt verstehe ich - Meine Frage hat sich mit Deiner Frage erledigt

Danke und Grüße Patrick