Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Kontextfreie Sprache
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Kontextfreie Sprache
 
Autor Nachricht
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 24 Jan 2009 - 16:13:14    Titel: Kontextfreie Sprache

Hallo,



Teil a) würde ich mit nem Gegenbeispiel widerlegen:
[;L1 =\lbrace a^{2n}b^{2n}|a,b \eps N \rbrace;]
[;L2 = \lbrace b^n|b \eps N \rbrace;]
Die sind beide kontextfrei.
Die Differenz ist:
[;L1 =\lbrace a^{2n}b^{n}|a,b \eps N \rbrace;],
was ja nicht kf ist, oder?

Wie kann ich das bei b) machen?

Grüße
rumpi

Edit:
Und, warum steht mein 2. Exponent immer höher als der 1.? [;a^nb^n;]

Edit2:

b) [;\overline {L1}\cup L2;] ist nicht immer kf ist richtig, denn

Sei
[;L3=\Sigma* \backslash L1=\overline {L1};]
Dann:
[;L3 \cup L2=L3;], weil L2 ja in L3 liegt. Und L3 brauch nicht regulär zu sein!?
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 24 Jan 2009 - 19:37:07    Titel:

Ist A\B denn nicht
A ohne die Elemente von B?
Daher mein Ansatz zwei kf Sprachen herzunehmen, deren Differenz dann nicht mehr kf ist.

Und zu b. Was ist denn das Komplement von z.b. a^n ?
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 24 Jan 2009 - 22:02:21    Titel:

Zitat:
Ist A\B denn nicht
A ohne die Elemente von B?
Daher mein Ansatz zwei kf Sprachen herzunehmen, deren Differenz dann nicht mehr kf ist.


Das ist richtig. Wie kommst du aber auf [;L1 =\lbrace a^{2n}b^{n}|a,b \eps N \rbrace;] ? Und wieso ist das nicht mehr kontextfrei?
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 24 Jan 2009 - 22:09:06    Titel:

Na wegen MINUS Very Happy
Ich dachte, a^2n b2^n ohne b^n ware einfach a^2n b^n
und a^2n b^n wäre nicht kf, denn beim aufpumpen könnte man mehr b's als a erzeugen oder mehr als doppelt soviele a's wie b's.
Bin vermutlich aufm Holzweg!?
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 24 Jan 2009 - 23:30:34    Titel:

Du schmeißt sehr viel durcheinander.

Zuerst einmal werden bei einer Mengendifferenz Elemente einer Menge weggelassen. Ein Element ist hier ein Wort. An den Wörtern selbst ändert sich nichts: Entweder es ist in der Differenz drin oder nicht.

Zum zweiten musst du, falls du das Pumping-Lemma verwenden willst, die Variante für kontextfreie Sprachen benutzen.
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 25 Jan 2009 - 11:15:50    Titel:

[;L1 =\lbrace a^{2n}b^{n}|a,b \eps N \rbrace;]

[;w=a^{2n}b^{n};]
mit w=uvxyz

[;v=a^i;]
[;y=\eps;]
Dann gilt für w=uv²xy²z

[;a^{2n+i}b^n \ni L1;]=> L1 ist nicht kf

So hatte ich mir das gedacht. Was das Komplement und die Differenz betrifft, das schaue ich mir noch mal an.
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 25 Jan 2009 - 11:59:21    Titel:

Also nun nochmal konkret eine Frage:

L1 = {a^n b^n; n = 1, 2, 3, . . . } ist kontextfrei.
Dass sie nicht regulär ist, glaub ich ja sofort, aber die Kontextfreiheit wundert mich, denn:

L2 = {a^n b^n c^n; n = 1, 2, 3, . . . } ist ja laut PL nicht kontextfrei.

Wieso kann ich L1 nicht auch nach den Kriterien des Pumping Lemmas "kaput" machen?
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 25 Jan 2009 - 15:17:36    Titel:

Achso, wusste nicht, dass u und y solche Formen annehmen dürfen.
Dann glaub ich das mal Smile

Edit:
Wie konstruiere ich mir am Besten 2 kf Sprachen, damit deren Differenz nicht mehr kf ist?
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 25 Jan 2009 - 16:02:38    Titel:

Zitat:
Dann glaub ich das mal

Besser wäre, wenn du es auch verstehst.

Zitat:
Wie konstruiere ich mir am Besten 2 kf Sprachen, damit deren Differenz nicht mehr kf ist?


Kennst du eine kontextfreie Sprache A, deren Komplement nicht kontextfrei ist? Dann benutze Folgendes:

[; \overline{A} = \Sigma^\ast \backslash A ;]
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 25 Jan 2009 - 16:09:29    Titel:

Nein, kenn ich leider nicht Sad
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Kontextfreie Sprache
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum