Komplement von endlichen Sprachen regulär?

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Komplement von endlichen Sprachen regulär?

Beitrag von patrix » 30. Aug 2010 19:58

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

nicolas
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 29. Jan 2010 12:56

Re: Komplement von endlichen Sprachen regulär?

Beitrag von nicolas » 30. Aug 2010 21:32

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

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Komplement von endlichen Sprachen regulär?

Beitrag von bruse » 30. Aug 2010 23:06

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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Komplement von endlichen Sprachen regulär?

Beitrag von patrix » 31. Aug 2010 10:35

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

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Komplement von endlichen Sprachen regulär?

Beitrag von bruse » 31. Aug 2010 11:45

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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Komplement von endlichen Sprachen regulär?

Beitrag von patrix » 31. Aug 2010 13:22

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

Danke und Grüße Patrick

Antworten

Zurück zu „Archiv“