Beweis kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:49 Mi 26.02.2014 | | Autor: | marcel25 |
| Aufgabe | | Ist die Sprache L = $ [mm] {a^n b^m a^n b^m | n,m > 0} [/mm] $ kontextfrei? Beweisen Sie Ihre Antwort! |
Mir ist durch eine Überlegung über einen Kellerautomaten Klar das diese Sprache nicht kontextfrei sein kann. Allerdings kann ich das durch einen Beweis mit dem puming lemma nicht Belegen.
Bei der Durchführung eines Widerspruchsbeweises mit dem pumping lemma hab ich folgendes Problem.
u [mm] v^i [/mm] w [mm] x^i [/mm] y darf ja nicht element von L sein.
Wenn ich aber v und x die b's zuordne kann ich solange "pumpen" wie ich will und es ergibt sich kein Widerspruch. Aber es muss ja jeder Fall einen Widerspruch erzeugen.
Kann jemand meinen Denkfehler identifizieren ?
Ich habe diese Frage in mit einem Tippfehler in der Aufgabenstellung in diesem Forum schon einmal gestellt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:08 Do 27.02.2014 | | Autor: | tobit09 |
Hallo marcel25!
> Ist die Sprache L = [mm]\{a^n b^m a^n b^m | n,m > 0\}[/mm]
> kontextfrei? Beweisen Sie Ihre Antwort!
> Mir ist durch eine Überlegung über einen Kellerautomaten
> Klar das diese Sprache nicht kontextfrei sein kann.
> Allerdings kann ich das durch einen Beweis mit dem puming
> lemma nicht Belegen.
>
> Bei der Durchführung eines Widerspruchsbeweises mit dem
> pumping lemma hab ich folgendes Problem.
> u [mm]v^i[/mm] w [mm]x^i[/mm] y darf ja nicht element von L sein.
> Wenn ich aber v und x die b's zuordne kann ich solange
> "pumpen" wie ich will und es ergibt sich kein Widerspruch.
> Aber es muss ja jeder Fall einen Widerspruch erzeugen.
>
> Kann jemand meinen Denkfehler identifizieren ?
Zunächst einmal gibt es ja durchaus nicht kontextfreie Sprachen, für die die Bedingung aus dem Pumping Lemma dennoch erfüllt ist. Auch ohne Denkfehler kann es also passieren, dass du eine Sprache als nicht kontextfrei nachweisen möchtest, aber dir das mithilfe des Pumping Lemmas nicht gelingt.
Bei dieser Aufgabe führt eine Argumentation mit dem Pumping Lemma aber zum Erfolg:
Angenommen die Sprache $L$ ist kontextfrei.
Dann existiert nach dem Pumping Lemma eine Zahl [mm] $n\in\IN$, [/mm] so dass für alle [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ eine Zerlegung $z=uvwxy$ existiert mit
1. [mm] $|vwx|\le [/mm] n$
2. [mm] $|v|,|x|\ge [/mm] 1$
3. [mm] $uv^iwx^iy\in [/mm] L$ für alle [mm] $i\in\IN_0$.
[/mm]
(Falls $n=0$, betrachten wir stattdessen $n=1$. Da $n=0$ in diesem Fall die obige Eigenschaft hat, hat $n=1$ erst Recht diese Eigenschaft.)
Insbesondere gilt diese Eigenschaft für das Wort
[mm] $z:=a^nb^na^nb^n\in [/mm] L$,
d.h. es existiert eine Zerlegung
[mm] $a^nb^na^nb^n=uvwxy$,
[/mm]
die 1., 2. und 3. genügt.
Wegen Eigenschaft 1. ist es nicht möglich, dass $v$ "aus vorderen b's von [mm] $a^nb^na^nb^n$ [/mm] besteht" und gleichzeitig $x$ "aus hinteren b's von [mm] $a^nb^na^nb^n$ [/mm] besteht".
Dein Problem tritt also bei der von mir durchgeführten Wahl von $z$ nicht auf.
Zu begründen bleibt natürlich noch ein Widerspruch.
Leider habe ich noch keine übersichtliche Art gefunden, den gewünschten Widerspruch herzuleiten.
Viele Grüße
Tobias
|
|
|
|
