Pumpinglemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Man beweise, daß die Sprache der Palindrome über {a, b}
L = { w | w [mm] \in [/mm] {a, b}* [mm] \wedge [/mm] w = [mm] w^{R} [/mm] } [mm] (w^{R} [/mm] : w gespiegelt)
nicht regulär ist. |
| Aufgabe 2 | Man zeige, daß die folgenden Sprachen [mm] L_{a} [/mm] und [mm] L_{b} [/mm] nicht von endlichen Automaten akzeptiert
werden können:
a) [mm] L_{a} [/mm] = { w | w [mm] \in [/mm] {a,b}* [mm] \wedge [/mm] #a(w) = #b(w)}
b) [mm] L_{b} [/mm] = { [mm] a^{p} [/mm] | p Primzahl } |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo, ihr schlauen Leute!
Ich habe Probleme mit dem Pumpinglemma. Und soweit ich weiß werden beide Aufgaben mit Hilfe dessen bewiesen. Ich hatte jedenfalls laut Bewertung beide Aufgaben komplett falsch und weiß auch nicht recht, wie die nun zu lösen sind, würde es aber gerne erfahren. Deswegen wär ich auch dankbar, falls mir jemand helfen kann. Prinzipiell weiß ich, wie das Pumpinglemma funktioniert, komme aber bei den Aufgaben nicht damit klar.
#a(w) bedeutet im übrigen die Anzahl der a's im Wort w.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:50 So 03.08.2008 | | Autor: | uliweil |
Hallo Heinzbert,
du hast ganz recht, diese Aufgaben sind mit dem Pumpinglemma zu lösen. Du schreibst, du wüsstest im Prinzip, wie das PL funktioniert. Dann weißt du sicherlich auch, dass das PL immer im indirekten Beweis benutzt wird:
Man nimmt an, die Sprache sei regulär und zeigt dann, dass dies zu einem Widerspruch führt.
Die entscheidende Aussage des PL ist, dass es eine natürliche Zahl (k oder wie auch immer sie heißen mag) gibt, für die ...usw.
Um diese Zahl k brauchst du dich nicht weiter zu kümmern, du darfst ihre Existenz als gegeben annehmen.
Deine Aufgabe ist es nun, ein Wort z der Sprache zu finden, das mindestens die Länge k hat, für das du zeigen kannst, dass es für jede Zerlegung z = uvw (mit den im PL angegebenen Eigenschaften) ein i gibt, sodass [mm] uv^{i}w [/mm] nicht in der Sprache liegt.
Bei der Suche nach einem solchen Wort z brauchst du mit der Länge nicht knauserig sein, es darf ruhig wesentlich länger als k sein.
In der ersten Aufgabe würde sich z.B. z = [mm] a^{k}ba^{k} [/mm] anbieten.
Für dieses Wort untersuchst du jetzt alle Zerlegungen in drei Teile u, v, w, wobei die Bedingungen sind, dass die ersten beiden Teile zusammen nicht länger als k sind und der zweite Teil nicht leer ist (also mindestens die Länge 1 hat). (Bei dem Wort z = [mm] a^{k}ba^{k} [/mm] bedeutet das, dass die beiden Teile u und v nur aus a's bestehen, wobei v mindestens ein a lang ist.)
Jetzt musst du noch ein i finden, sodass das Wort z' = [mm] uv^{i}w [/mm] nicht in der Sprache liegt.
Beliebte Kandidaten für i sind i = 0 oder i = 2.
In diesem Beispiel geht jedes i ( [mm] \not= [/mm] 1 natürlich).
Such dir ein i aus und schreibe das Wort z' mal hin, dann solltest du erkennen, dass es kein Palindrom ist, also nicht in der Sprache liegt.
Damit ist die Aussage des PL nicht erfüllt und deine Annahme, die Sprache sei regulär gewesen, zum Widerspruch geführt.
Aufgabe 2 a) geht ganz ähnlich:
- Suche dir ein Wort der Länge k, das in der Sprache liegt,
- zerlege es in drei Teile u, v und w und überlege dir, wie die Teile aussehen müssen, wenn sie die Eigenschaften aus dem PL erfüllen wollen
- finde ein i , sodass [mm] uv^{i}w [/mm] nicht in der Sprache liegt.
Auch Aufgabe 2 b) geht nach diesem Schema, hier ist nur die Suche nach dem i etwas schwieriger.
|
|
|
| |
|
Vielen Dank für deine Antwort.
Irgendwie muss mir wohl entgangen sein, dass man sich ein Wort beliebiger Gestalt aus der Sprache aussuchen kann für die Untersuchung. Ich hatte irgendwie angenommen, dass man irgendeine allgemeine Form benutzen muss, die quasi alle Wörter darstellt, weil in den Beispielen immer solche Sprachen benutzt wurden, bei denen das so einfach funktioniert; wie [mm] a^{n}b^{n}.
[/mm]
Heißt das, dass ich für 2 a) einfach sowas nehmen kann wie eben jenes [mm] a^{n}b^{n}, [/mm] weil es ja genauso viele a's wie b's hat?
Wenn ich das dann wieder in uvw zerlege, sodass eben u und v nur aus a's bestehen (wegen |uv| [mm] \le [/mm] n), und dann [mm] uv^{2}w [/mm] wähle, wurde ja nur der a-Bereich gepumpt, wodurch dann mehr a's als b's im Wort sind und das Wort nicht mehr zu der Sprache gehört. Also ist die Sprache nicht regulär und kann nicht von einem endlichen Automaten akzeptiert werden.
Stimmt das so, oder habe ich was falsch verstanden bei der Wahl des Wortes zur Untersuchung?
Genauso würden ja dann in der 1. Aufgabe in dem von dir gewählten Wort [mm] a^{n}ba^{n} [/mm] mit [mm] uv^{2}w [/mm] links vom b mehr a's als auf der rechten Seite sein, wodurch es kein Palindrom mehr ist und somit die Sprache nicht regulär ist.
Bei der Aufgabe 2 b) hab ich ein Problem:
Wie mache ich das da mit dem n? Kann ich einfach sagen: Ich nehme das Wort [mm] a^{n} [/mm] mit n = Primzahl? Für jede Primzahl > 2 würde das Wort eine ungerade Anzahl an a's haben und jede Zerlegung uvw mit dem Pumping [mm] uv^{2}w [/mm] würde bedeuten, dass das Wort um ein Symbol länger geworden ist und somit eine Länge m hat mit m : gerade Zahl, was ja keine Primzahl ist, wegen Teilbarkeit mit 2. Wodurch das Wort nicht mehr zu der Sprache ghört.
Geht das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:53 So 03.08.2008 | | Autor: | uliweil |
> Vielen Dank für deine Antwort.
> Irgendwie muss mir wohl entgangen sein, dass man sich ein
> Wort beliebiger Gestalt aus der Sprache aussuchen kann für
> die Untersuchung.
So ist es.
Ich hatte irgendwie angenommen, dass man
> irgendeine allgemeine Form benutzen muss, die quasi alle
> Wörter darstellt, weil in den Beispielen immer solche
> Sprachen benutzt wurden, bei denen das so einfach
> funktioniert; wie [mm]a^{n}b^{n}.[/mm]
Das PL behauptet ja, dass es für alle Wörter der Sprache eine Zerlegung gibt mit ...
Im indirekten Beweis wird daraus dann: es genügt, ein Wort zu finden, so dass für alle Zerlegungen dieses Wortes mit ...
>
> Heißt das, dass ich für 2 a) einfach sowas nehmen kann wie
> eben jenes [mm]a^{n}b^{n},[/mm] weil es ja genauso viele a's wie b's
> hat?
Genau! Aber achte auf die Bezeichnungen. Ist n die Konstante aus dem PL (die bei mir k hieß?) Dann ist es richtig. Wichtig ist: das Wort, das du wählst, muß mindestens die Länge der Konstanten aus dem PL haben.
> Wenn ich das dann wieder in uvw zerlege, sodass eben u und
> v nur aus a's bestehen (wegen |uv| [mm]\le[/mm] n), und dann [mm]uv^{2}w[/mm]
> wähle, wurde ja nur der a-Bereich gepumpt, wodurch dann
> mehr a's als b's im Wort sind und das Wort nicht mehr zu
> der Sprache gehört. Also ist die Sprache nicht regulär und
> kann nicht von einem endlichen Automaten akzeptiert
> werden.
> Stimmt das so, oder habe ich was falsch verstanden bei der
> Wahl des Wortes zur Untersuchung?
>
Genau so ist es korrekt!
> Genauso würden ja dann in der 1. Aufgabe in dem von dir
> gewählten Wort [mm]a^{n}ba^{n}[/mm] mit [mm]uv^{2}w[/mm] links vom b mehr a's
> als auf der rechten Seite sein, wodurch es kein Palindrom
> mehr ist und somit die Sprache nicht regulär ist.
>
Richtig!
> Bei der Aufgabe 2 b) hab ich ein Problem:
> Wie mache ich das da mit dem n? Kann ich einfach sagen:
> Ich nehme das Wort [mm]a^{n}[/mm] mit n = Primzahl?
Ja, obwohl ich wieder nicht sicher bin, ob du mit deinen Bezeichnungen richtig liegst: Die Sprache besteht aus allen [mm] a^{p} [/mm] mit p prim. Das PL sagt, dass es eine Konstante n (oder k) gibt usw. Das Wort, das du wählst, muss in der Sprache liegen und mindestens die Länge n haben. Es geht also nicht jede Primzahl, sondern du musst eine nehmen, die größer ist als n. (Das ist ja zum Glück kein Problem, denn es gibt ja genügend große Primzahlen.) Wähle eine (ich nenne sie jetzt mal q), und dann hast du dein Wort, das du untersuchst.
Für jede
> Primzahl > 2 würde das Wort eine ungerade Anzahl an a's
> haben und jede Zerlegung uvw mit dem Pumping [mm]uv^{2}w[/mm] würde
> bedeuten, dass das Wort um ein Symbol länger geworden ist
Das stimmt nicht. Das Aufpumpen verlängert das Wort um die Länge des Teilwortes v. Und über die weißt du nur, dass sie zwischen 1 und dieser Konstanten n bzw. k liegt. Hier hast du auch nicht die Freiheit, das v in bestimmter Weise festzulegen, denn du musst zeigen, dass es für jede Zerlegung (also hier: für jedes v aus [mm] \{a, a^{2}, ... a^{n} \}) [/mm] ein i gibt, sodass das neue Wort nicht in der Sprache liegt.
> und somit eine Länge m hat mit m : gerade Zahl, was ja
> keine Primzahl ist, wegen Teilbarkeit mit 2. Wodurch das
> Wort nicht mehr zu der Sprache ghört.
> Geht das so?
Nicht ganz, aber deine Idee ist richtig: Man kann ein i angeben, so dass die Länge von [mm] uv^{i}w [/mm] mit Sicherheit keine Primzahl ist. Dieses i ist aber von der Länge von v abhängig.
Dein Wort ist von der Gestalt [mm] a^{r}a^{s}a^{t}, [/mm] wobei 1 [mm] \le [/mm] s [mm] \le [/mm] n ist und r+s+t = q (die oben gewählte Primzahl).
Durch das Aufpumpen erhälst du ein Wort der Länge r+is+t.
Deine Aufgabe ist nun noch, i so zu wählen, dass dieser Ausdruck auf jeden Fall keine Primzahl ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:10 So 03.08.2008 | | Autor: | Heinzbert |
Achja, hatte vergessen, dass die Länge von v ja nicht feststeht, sondern beliebige Größe zw. 1 und n hat.
Und ja, dein k heißt bei uns n. Hatte deswegen n benutzt aus Gewohnheit.
Vielen Dank noch mal für deine Antworten. Sie haben mir sehr beim Verständnis des Lemmas und der Anwendung geholfen. Danke.
|
|
|
|
