Pumping Lemma Problem

18.09.2013, 11:28	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: $\begin{eqnarray} L = {a^{n} b^{m} : a,b \in \mathbb N } \end{eqnarray}$ 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: $\begin{eqnarray} L = {a^{n}b^{n} : n\in \mathbb N } \end{eqnarray}$ 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 $\begin{eqnarray} L=a^nb^n \end{eqnarray}$ ist, wie du schon richtig erkannt hast, nicht regulär. Egal wie du $\begin{eqnarray} v \end{eqnarray}$ wählst, wenn du anfängst zu pumpen, dann ist $\begin{eqnarray} uv^iw \end{eqnarray}$ nicht mehr in $\begin{eqnarray} L \end{eqnarray}$ . Egal ob $\begin{eqnarray} v \end{eqnarray}$ nur aus $\begin{eqnarray} a \end{eqnarray}$ 's, aus $\begin{eqnarray} ab \end{eqnarray}$ 's oder aus $\begin{eqnarray} b \end{eqnarray}$ 's besteht. Es muss ja für alle $\begin{eqnarray} i \end{eqnarray}$ aus $\begin{eqnarray} N_0 \end{eqnarray}$ 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 $\begin{eqnarray} \|z\|\ge n' \end{eqnarray}$ muss mit PL folgendes gezeigt werden: 1.Fall: $\begin{eqnarray} u = \epsilon \end{eqnarray}$ : - $\begin{eqnarray} v \end{eqnarray}$ besteht nur aus $\begin{eqnarray} a \end{eqnarray}$ 's - $\begin{eqnarray} v \end{eqnarray}$ besteht aus $\begin{eqnarray} a \end{eqnarray}$ 's und $\begin{eqnarray} b \end{eqnarray}$ 's 2.Fall: $\begin{eqnarray} u = a \end{eqnarray}$ 's: - $\begin{eqnarray} v \end{eqnarray}$ besteht nur aus $\begin{eqnarray} a \end{eqnarray}$ 's - $\begin{eqnarray} v \end{eqnarray}$ besteht aus $\begin{eqnarray} a \end{eqnarray}$ 's und $\begin{eqnarray} b \end{eqnarray}$ 's - $\begin{eqnarray} v \end{eqnarray}$ besteht nur aus $\begin{eqnarray} b \end{eqnarray}$ 's 3.Fall: $\begin{eqnarray} u = a \end{eqnarray}$ 's und $\begin{eqnarray} b \end{eqnarray}$ 's: - $\begin{eqnarray} v \end{eqnarray}$ besteht nur aus $\begin{eqnarray} b \end{eqnarray}$ 's Bisher hast du es nur gezeigt für $\begin{eqnarray} u=a \end{eqnarray}$ und $\begin{eqnarray} v=a \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »