Seite 1 von 1

Komplement von endlichen Sprachen regulär?

Verfasst: 30. Aug 2010 19:58
von patrix
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

Re: Komplement von endlichen Sprachen regulär?

Verfasst: 30. Aug 2010 21:32
von nicolas
Endliche Sprachen sind AFAIK immer regulär, womit auch ihr Komplement regulär ist.

Re: Komplement von endlichen Sprachen regulär?

Verfasst: 30. Aug 2010 23:06
von bruse
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.

Re: Komplement von endlichen Sprachen regulär?

Verfasst: 31. Aug 2010 10:35
von patrix
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

Re: Komplement von endlichen Sprachen regulär?

Verfasst: 31. Aug 2010 11:45
von bruse
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.

Re: Komplement von endlichen Sprachen regulär?

Verfasst: 31. Aug 2010 13:22
von patrix
O.K. jetzt verstehe ich - Meine Frage hat sich mit Deiner Frage erledigt :)

Danke und Grüße Patrick