Pumping Lemma Problem |
18.09.2013, 11:28 | Shizophren | Auf diesen Beitrag antworten » |
Pumping Lemma Problem Vielleicht mache ich es auch richtig, weiß aber nicht genau. Nehmen wir an, ich habe folgende Sprache: 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 (a)^2 b = a aa bb Somit wäre die Sprache ja regulär. Wende ich das korrekt an? |
||
18.09.2013, 11:47 | jimmyt | Auf diesen Beitrag antworten » |
@Shizophren : Also die Sprache ist regulär. Ich habe mir eben einen ganz einfachen Automaten gezeichnet. Man braucht nur 3 Zustände. Das Pumping sieht nicht schlecht aus, aber warum sind am Ende auf einmal 2 b's vorhanden? |
||
18.09.2013, 11:53 | Shizophren | Auf diesen Beitrag antworten » |
Da hatte ich wohl einen Zitterich am B :-) Da gehört nur 1 B hin. Aber vom Verständnis her korrekt? Wie sähe es denn bei sowas hier aus: Da sieh man ja schon, dass es keine reg. Sprache ist. Aber man muss das ja Anhand des PL's beweisen. Nehme ich hier jetzt mal n=2, dann hätte ich als Wort aabb u = a v = a b = bb v >=0 uv <= n uv^n^2b --> a a^n*2 bb und ein Wort wie a aaaaa bb gehört nicht zur Sprache. |
||
18.09.2013, 12:14 | jimmyt | Auf diesen Beitrag antworten » |
@Shizophren : Die Sprache ist, wie du schon richtig erkannt hast, nicht regulär. Egal wie du wählst, wenn du anfängst zu pumpen, dann ist nicht mehr in . Egal ob nur aus 's, aus 's oder aus 's besteht. Es muss ja für alle aus gelten. Und das ist nicht der Fall. Deswegen keine reguläre Sprache. |
||
18.09.2013, 17:47 | jimmyt | Auf diesen Beitrag antworten » |
@Shizophren : Waren meine Postings hilfreich? Vielleicht nochmal ein bischen ausführlicher: Bspw. für muss mit PL folgendes gezeigt werden: 1.Fall: : - besteht nur aus 's - besteht aus 's und 's 2.Fall: 's: - besteht nur aus 's - besteht aus 's und 's - besteht nur aus 's 3.Fall: 's und 's: - besteht nur aus 's Bisher hast du es nur gezeigt für und . |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |