Komplement von endlichen Sprachen regulär?
Verfasst: 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
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