Pumping Lemma Problem

Neue Frage »

Shizophren Auf diesen Beitrag antworten »
Pumping Lemma Problem
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:



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?
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?
 
 
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.
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. Augenzwinkern
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 .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »