kontextfreies Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:29 Mo 08.12.2008 | | Autor: | myo |
| Aufgabe 1 | Ist die folgende Sprachen ist kontextfrei?
[mm]L_{1}=\{a^nb^m|0\le{n}\le{m}\le{2n}\}[/mm] |
| Aufgabe 2 | Ist die folgende Sprachen ist kontextfrei?
[mm]L_{2}=\{baba^2ba^3b...ba^{n-1}ba^nb|n\ge1\}[/mm] |
Hi,
kann mir vielleicht jemand einen kleinen Tipp geben wie ich genau an die beiden Aufgaben rangehen soll oder was denn hier vorteilhaft wäre?
Ich kenne zwar das Pumping-Lemma für kontextfreie Sprachen, aber mir fällt der Umgang damit noch recht schwer.
Vorgehensweise:
Ich nehme mir ein Wort aus der Sprache L und zerlege es dann nach den vorgegebenen Regeln des Pumping-Lemmas und führe es dann zu einem Widerspruch beim pumpen, sofern die Sprache nicht kontextfrei sei.
Reicht es dabei aus eine Zerlegung des Wortes zu finden die nicht pumpbar ist oder muss ich das für alle möglichen Zerlegungen des Wortes zeigen, dass diese nicht pumpbar sind?
Meine Überlegung zur Aufgabe 1 ist, dass ich das Wort [mm]a^lb^l[/mm] nehme, welches ja in der Sprache ist, wobei l meine Pumping-Zahl sein soll. Reicht das dann aus eine Zerlegung zu zeigen die nicht pumpbar ist, sofern es eine gibt, oder alle möglichen?
Zu Aufgabe 2 dachte ich mir das ich das vielleicht über die verkettung von kontextfreien Sprachen zeigen kann.
Aber das sind nur zwei kleine Überlegungen. Ich weiss einfach nicht so recht wie ich da rangehen soll/kann.
Hoffe das mir dabei jemand weiterhelfen kann.
Gruss
Martin
PS: Ich habe diese Frage in keinem anderen Forum oder auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:09 Di 09.12.2008 | | Autor: | bazzzty |
> Ist die folgende Sprachen ist kontextfrei?
>
> [mm]L_{1}=\{a^nb^m|0\le{n}\le{m}\le{2n}\}[/mm]
> ...
> Ich kenne zwar das Pumping-Lemma für kontextfreie
> Sprachen, aber mir fällt der Umgang damit noch recht
> schwer.
> Vorgehensweise:
> Ich nehme mir ein Wort aus der Sprache L und zerlege es
> dann nach den vorgegebenen Regeln des Pumping-Lemmas und
> führe es dann zu einem Widerspruch beim pumpen, sofern
> die Sprache nicht kontextfrei sei.
Soweit richtig, aber...
> Reicht es dabei aus eine Zerlegung des Wortes zu finden
> die nicht pumpbar ist oder muss ich das für alle
> möglichen Zerlegungen des Wortes zeigen, dass diese
> nicht pumpbar sind?
Letzteres. Das Pumping-Lemma sagt, daß es eine Zerlegung gibt. Du mußt deshalb zeigen, daß jede Zerlegung dem Pumping-Lemma "widerspricht", um zu zeigen, daß die Sprache nicht kontextfrei ist.
>
> Meine Überlegung zur Aufgabe 1 ist, dass ich das Wort
> [mm]a^lb^l[/mm] nehme, welches ja in der Sprache ist,
> wobei l meine Pumping-Zahl sein soll. Reicht das dann
> aus eine Zerlegung
> zu zeigen die nicht pumpbar ist, sofern es eine gibt,
> oder alle möglichen?
Siehe oben. Du kannst Dir nicht eine Zerlegung aussuchen. Du willst zeigen, daß es keine Zerlegung gibt.
Bevor Du aber anfängst, mit dem Pumping-Lemma zu argumentieren, schau Dir die Sprache nochmal an! Versuch doch mal, sie zu erzeugen! Vielleicht ist sie ja kontextfrei? Ist auch mein allgemeiner Tipp: Erst probieren, konstruktiv zu arbeiten, dann erst Beweise konstruieren.
> Ist die folgende Sprachen ist kontextfrei?
>
> [mm]L_{2}=\{baba^2ba^3b...ba^{n-1}ba^nb|n\ge1\}[/mm]
> Zu Aufgabe 2 dachte ich mir das ich das vielleicht über > die verkettung von kontextfreien Sprachen zeigen kann.
Das wäre leider wieder das falsche Pferd.
> Aber das sind nur zwei kleine Überlegungen. Ich weiss
> einfach nicht so recht wie ich da rangehen soll/kann.
Mein Tipp wäre: Erstmal versuchen, eine Grammatik zu finden. Das ist im ersten Fall gar nicht so schwer. Im zweiten wirst Du scheitern (aber es schadet nie, zumindest darüber nachzudenken, warum das so schwerfällt).
Dann überlegen, warum es nicht geht. Du hast das Pumping-Lemma noch nicht so recht verinnerlicht, glaube ich. Ich werde es hier auch nicht in zwei Worten zusammenfassen können, aber die Beweisstruktur muß sitzen:
Pumping-Lemma: Es gibt eine Zerlegung mit ..., für die gilt, daß für alle i .... in L.
Beweis, daß eine Sprache nicht kontextfrei ist: Für jede Zerlegung mit ... gilt: Es gibt ein i, so daß ... nicht in L. (Sprich: Das Pumping-Lemma ist bei dieser Sprache nicht anwendbar!)
Mal an den beiden Sprachen oben:
Mach Dir klar, daß [mm]a^{n-1} ab b^{m-1}[/mm] eine Zerlegung ist, die dem Pumping-Lemma entspricht (Vorsicht: [mm]w=\epsilon[/mm])
Zur zweiten Sprache: Die ist wirklich schwerer, weil man es auch am leichtesten "etwas um die Ecke" beweist.
Die Idee ist folgende: Egal, wie ich zerlegt habe: Wenn ich pumpe, steigt die Länge des Wortes linear in i. Das kann aber nicht sein, denn die zulässigen Wortlängen steigen quadratisch!
So sieht so ein Beweis aus:
Annahme: L ist kontextfrei. Dann sei [mm]n,u,v,w,x,y[/mm] ensprechend dem Pumping-Lemma gewählt[1].
Jetzt sei [mm]c:=|vx|[/mm] und [mm]k:=|uvwxy|[/mm]. Die entprechend dem Pumping-Lemma gebildeten Worte [mm]uv^iwx^iy[/mm] haben die Längen [mm]k+(i-1)c[/mm].
"Gepumpte Wörter" liegen also immer um Länge [mm]c[/mm] auseinander. Wörter in [mm]L[/mm] haben ansteigende Abstände 1,2,3... Es gibt also zwei Worte [mm]l_1,l_2\in L[/mm] so, daß [mm]k\leq |l_1|< |l_1|+c<|l_2|[/mm], ohne daß es ein Wort [mm]l^\star[/mm] gibt mit [mm]|l_1|< |l^\star|<|l_2|[/mm]. Eines der gepumpten Wörter muß aber eine Länge zwischen [mm]|l_1|[/mm] und [mm]|l_2|[/mm] haben, kann also nicht in der Sprache liegen.
[1] Es kann sein, daß das ausführlicher gefordert wird: Dann sei n entprechend dem Pumping-Lemma gewählt, und uvwxy die Zerlegung eines Wortes mit [mm]|uvwxy|\geq n[/mm], die dem Pumping-Lemma entspricht.
|
|
|
|
