Pumping Lemma für reg. Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | [mm] L=\{a^n*b^m : a,b \in\IN\} [/mm] |
Ich habe ein Problem, das Pumping Lemma für reguläre Sprachen zu verstehen.
Vielleicht mache ich es auch richtig, weiß aber nicht genau.
Nehmen wir an, ich habe folgende Sprache:
[mm] L=\{a^{n} b^{m} : a,b \in\IN\}
[/mm]
Damit kann ich ja Wörter bilden wie
bei n = 3, m = 2 --> aaabb
Wenn ich dazu jetzt das Pumping Lemma anwende mit uvw Zerteilung, zerteile ich dann hier korrekt?
Nehme ich als Pumping-Länge n=2 habe ich folgendes
u = a
vw = a
w = b
Die Regeln sagen ja
u>=0 --> ist gegeben
uv<=n --> ist auch gegeben weil uv hier a ist und n=2 also ist uv kleiner n
Pumping Lemma angewendet
uv^2w = a [mm] (a)^2 [/mm] b = a aa bb
Somit wäre die Sprache ja regulär.
Wende ich das korrekt an?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[http://www.matheboard.de/thread.php?threadid=528053]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:40 Fr 20.09.2013 | | Autor: | tobit09 |
Hallo shizophren und herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> [mm]L=\{a^n*b^m : a,b \in\IN\}[/mm]
>
> Ich habe ein Problem, das Pumping Lemma für reguläre
> Sprachen zu verstehen.
Am besten, du postest mal eure genaue Formulierung dieses Pumping Lemmas. Dann kann man besser darauf eingehen.
> Vielleicht mache ich es auch richtig, weiß aber nicht
> genau.
Was möchtest du denn eigentlich tun? Nachweisen, dass obige Sprache regulär ist? Oder die Folgerung des Pumping Lemmas an diesem Beispiel nachvollziehen?
> Nehmen wir an, ich habe folgende Sprache:
>
> [mm]L=\{a^{n} b^{m} : a,b \in\IN\}[/mm]
>
> Damit kann ich ja Wörter bilden wie
>
> bei n = 3, m = 2 --> aaabb
Ja.
> Wenn ich dazu jetzt das Pumping Lemma anwende mit uvw
> Zerteilung, zerteile ich dann hier korrekt?
Was meinst du mit "Pumping Lemma anwenden" hier genau?
> Nehme ich als Pumping-Länge n=2
Achtung: Den Buchstaben $n$ aus dem Pumping Lemma nicht mit dem Buchstaben $n$ aus der Definition von $L$ verwechseln!
> habe ich folgendes
>
> u = a
> vw = a
$v=a$ meinst du sicherlich.
> w = b
Du betrachtest also im Moment das Wort $aab$?
> Die Regeln sagen ja
> u>=0 --> ist gegeben
> uv<=n --> ist auch gegeben weil uv hier a ist und n=2 also
> ist uv kleiner n
Im Pumping Lemma heißt es "$|v|>0$ und [mm] $|uv|\le [/mm] n$", nicht [mm] "$u\ge0$ [/mm] und [mm] $uv\le [/mm] n$".
> Pumping Lemma angewendet
>
> uv^2w = a [mm](a)^2[/mm] b = a aa bb
> Somit wäre die Sprache ja regulär.
Nein, das hast du nicht begründet. Das Pumping Lemma sagt dir nur: Wenn wir von einer Sprache schon wissen, dass sie regulär ist, dann genügt sie der Folgerung aus dem Pumping Lemma. Daher kann man mit dem Pumping Lemma grundsätzlich nicht die Regularität einer Sprache nachweisen.
Dagegen ist es schon möglich, mit dem Pumping Lemma die Nicht-Regularität einer Sprache nachzuweisen: Man nimmt widerspruchshalber an, die Sprache wäre regulär. Dann würde sie der Folgerung aus dem Pumping Lemma genügen. Das gilt es dann zu einem Widerspruch zu führen.
Viele Grüße
Tobias
|
|
|
|
