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
Komplement von endlichen Sprachen regulär?
Re: Komplement von endlichen Sprachen regulär?
Endliche Sprachen sind AFAIK immer regulär, womit auch ihr Komplement regulär ist.
Re: Komplement von endlichen Sprachen regulär?
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.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Re: Komplement von endlichen Sprachen regulär?
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
Viele Grüße Patrick
Re: Komplement von endlichen Sprachen regulär?
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.
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.
Re: Komplement von endlichen Sprachen regulär?
O.K. jetzt verstehe ich - Meine Frage hat sich mit Deiner Frage erledigt 
Danke und Grüße Patrick

Danke und Grüße Patrick