Abschlusseigenschaften und Chomsky-Hierarchie

bafnai
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 126
Registriert: 13. Apr 2011 06:36

Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von bafnai » 21. Aug 2011 13:39

Hallo,
ich habe drei Fragen bezüglich der Abschlusseigenschaften und der Chomsky-Hierarchie.

Frage 1:
Gegeben sind zwei Sprachen:
Sprache 1 ist unter einer bestimmten Operation abgeschlossen.
Sprache 2 ist unter derselben Operation nicht abgeschlossen.

Sprache 1 wird nun mit der Operation auf Sprache 2 angewandt (bzw. andersherum).
Welchen Typ hat das Ergebnis?

Als Beispiel: Sprache 1 ist von Typ 3, Sprache 2 ist von Typ 2, die Operation ist Durchschnitt.


Frage 2:
Auf zwei Sprachen desselben Typs (z. B. Typ 2) wird eine Operation angewandt, unter der die Sprachen nicht abgeschlossen sind (z. B. Komplement). Welchen Typ hat das Ergebnis?

Frage 3:
Auf zwei Sprachen unterschiedlichen Typs (z. B. Typ 3 und 2) wird eine Operation angewandt, unter der die Sprachen abgeschlossen sind (z. B. Vereinigung). Welchen Typ hat das Ergebnis?


MfG bafnai

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von Domac » 21. Aug 2011 14:34

Servus,

zu Frage 1):
Sie \(L_1\) kontextfrei und \(L_2\) regulär und nun möchtest du \(L_1 \cap L_2\) beispielsweise als Operation. Nun sind reguläre Sprachen auch insbesondere kontextfreie Sprachen (siehe Chomsky-Hierarchie). Wendest du nun die Durschnittsoperation auf eine Srache vom Typ3 und eine andere Sprache vom Typ2 (nicht abgeschlossen hier) an, wird wohl eine Sprache vom Typ1 dabei herauskommen. Wobei ich mir nicht sicher bin, ob es in Spezialfällen auch in einer Typ2 oder Typ3 Sprache resultieren kann. Aber allgemein: Es kommt weder ein Sprache vom Typ3, noch 2 dabei heraus.

zu Frage 2):
Der Typ erfährt ein downgrade. ;)
(Zu deinem Beispiel ... Typ1)

zu Frage 3):
Vereinigst du nun eine Sprache vom Typ3 und eine Sprache vom Typ2, dann erhälst du resultierend eine Sprache vom Typ2.

Gruß domac
Extend my dropbox space (here).
Thanks!

bafnai
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 126
Registriert: 13. Apr 2011 06:36

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von bafnai » 21. Aug 2011 16:28

Hallo,
erst einmal vielen Dank für die schnelle und ausführliche Antwort.
Domac hat geschrieben:Wobei ich mir nicht sicher bin, ob es in Spezialfällen auch in einer Typ2 oder Typ3 Sprache resultieren kann. Aber allgemein: Es kommt weder ein Sprache vom Typ3, noch 2 dabei heraus.
Kann man auch feststellen welchen Typ das Ergebnis genau hat?
Denn der Hintergedanke der Frage waren die Richtig/Falsch-Klausuraufgaben.
Als Beispiel: Der Durchschnitt einer regulären und einer kontextfreien Sprache ist entscheidbar.
Hier muss man genau wissen, ob das Ergebnis noch mindestens Typ 1 hat oder schon darunter liegt.

Und eine weitere Frage:
Typ 0-Sprachen sind bekanntlich nicht unter Komplement abgeschlossen.
Welche Form hat das Ergebnis, wenn ein Komplement auf eine Typ 0-Sprache angewandt wird?

MfG bafnai

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von Domac » 21. Aug 2011 17:45

Servus,
Sprachen vom Typ 0 sind unter Komplement nicht abgeschlossen, da sie sonst entscheidbar wären.
Gruß domac

EDIT: Zu Frage 1 nochmal... ich habe mir überlegt, dass wenn man zwei kontextfreie Sprachen unter einer nicht abgeschlossenen Operation (durchschnitt) durchführt, man eine kontextsensitive erhält. Dann das ganze auf das Fallbeispiel übertragen. Eine "genaue Anleitung" habe ich nicht befolgt, mehr das Bauchgefühl gefragt. :lol:
Extend my dropbox space (here).
Thanks!

bafnai
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 126
Registriert: 13. Apr 2011 06:36

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von bafnai » 22. Aug 2011 06:09

Hallo.
Domac hat geschrieben:Servus,
Sprachen vom Typ 0 sind unter Komplement nicht abgeschlossen, da sie sonst entscheidbar wären.
Aber ist das Komplement einer Typ 0 Sprache immer noch von Typ 0 oder wird es überhaupt nicht mehr von einer Grammatik erzeugt?

MfG bafnai

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von dschneid » 22. Aug 2011 10:55

Im Allgemeinen eben nicht. Die Typ-0-Sprachen sind gerade die rekursiv aufzählbaren bzw. die semi-entscheidbaren Sprachen, und es gibt viele Beispiele für solche Sprachen, deren Komplement nicht rekursiv aufzählbar und deswegen auch nicht vom Typ 0 ist, konkret zum Beispiel das Halteproblem (denn es lässt sich semi-entscheiden, ob ein Programm hält, indem man es einfach laufen lässt, aber ob ein Programm endlos läuft lässt sich nicht einmal semi-entscheiden).

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von Ankou » 23. Aug 2011 12:07

Wobei ich mir nicht sicher bin, ob es in Spezialfällen auch in einer Typ2 oder Typ3 Sprache resultieren kann. Aber allgemein: Es kommt weder ein Sprache vom Typ3, noch 2 dabei heraus.
Da ein Durchschnitt von zwei Typ 3 Sprachen auch ein Durchschnitt zischen einer Typ2 und einer Typ3 Sprache ist hast du da schonmal einen Spezialfall. Ist die eine Sprache eine Teilmenge der anderen hast du da einen weiteren Spezialfall, weniger absonderliche Fälle fallen mir grad nicht einfach so ein. Der Beweis im Script ist aber eben nur ein Gegenbeispiel, es ist also nicht so, dass unter bestimmten Voraussetzungen definitiv keine Typ3 oder Typ2 Sprache herauskommt.

nochmal an den Threadersteller(falls es noch nicht ganz klar geworden ist, ansonsten sry für die Wiederholung):
Prinzipiell gilt Vereinigung Typ 3 und Typ 2 ~ kennen wir keine besondere abgeschlossene Operation(wird es im allgemeinen vermutlich auch nicht geben, haben wir aber mW nirgens bewiesen), Typ 3 ist aber auch Typ 2 also
Vereinigung Typ 2 und Typ 2 ~ nicht abgeschlossen, wir wissen also nur, dass keine Typ 2 Sprache dabei rauskommen muss. Typ 2 Sprachen sind aber auch Typ 1 Sprachen, also ist eine Vereinigung von Typ 2 und Typ 2 auch eine Vereinigung von Typ 1 und Typ 1, die ist abgeschlossen, also muss eine Typ 1 Sprache dabei rauskommen.

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von dschneid » 23. Aug 2011 20:10

Ich möchte mal anmerken, dass alle drei ursprünglichen Fragen nicht allgemein beantwortet werden können. Es kommt auf die konkreten Typen der beteiligten Sprachen an, sogar auf die konkreten Sprachen selbst, nicht alleine darauf, ob diese Typen unter der Operation abgeschlossen sind.

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von kain » 31. Aug 2011 14:40

http://de.wikipedia.org/wiki/Chomsky-Hi ... 9Cbersicht

Kann man mit Hilfe dieser Übersicht solche Fragen beantworten, wie z.B.:

Ist Komplement einer kontextfreien Sprache entscheidbar?

(Und andere Ankreuzaufgaben, die ähnlich sind).

Ich würd jetzt auf die obere Frage mit "nein" Antworten. Denn Typ-2 ist unter Komplement nicht abgeschlossen.

Aber wie sieht es jetzt mit denen hier aus:

Durchschnitt einer regulären Sprache mit einer beliebigen Sprache ist regulär.
Vereinigung einer regulären Sprache mit einer kontextfreien Sprache ist regulär.
Vereinigung einer regulären Sprache mit einer kontextfreien Sprache ist kontextfrei.

?

Typ-0 und Typ-3 ist unter Durschnitt abgeschlossen => regulär
Typ-0 und Typ-2 ist unter Vereinigung abgeschlossen => regulär (und kontextfrei)
Typ-0 und Typ-2 ist unter Vereinigung abgeschlossen => kontextfrei (und regulär)

?

Was passiert wenn die eine Sprache abgeschlossen ist, aber nicht die andere?

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Abschlusseigenschaften und Chomsky-Hierarchie

Beitrag von Ankou » 31. Aug 2011 15:21

Eine tabellarische Übersicht zur Abgeschlossenheit gibts auch im Script auf Seite 70
Ist Komplement einer kontextfreien Sprache entscheidbar?
Typ 1 ist abgeschlossen unter Komplement. Das Komplement einer Typ 2 Sprache ist somit auf jeden Fall eine Typ 1 Sprache. Typ 1 Sprachen sind außerdem entscheidbar.

Antworten

Zurück zu „Archiv“