Pumping Lemma

07.11.2012, 16:21

Shaggz

Pumping Lemma

Meine Frage:
Hey Hallo Leute,
Ich habe mal eine Frage zum Pumping Lemma. Also ich verstehe den Sinn hinter dem Pumping Lemma: Es geht darum zu zeigen, dass bestimmte Sprachen nicht regulär sind. Das macht man dann mithilfe einer Wortzerlegung in w=xyz. Findet man eine Zerlegung, die nicht von der Sprache akzeptiert wird, hat man gezeigt, dass die Sprache nicht regulär ist.

So nun ist meine Aufgabe explizit anzugeben, wie die Sprache die alle Wörter mit "aba" (Das Alphabet besteht nur aus a´s und b´s) als Teilwort akzeptiert, pumpbar ist. Ich weiß hierbei dass es sich logischerweise um eine reguläre Sprache handelt, da ich einen Automaten für diese zeichnen kann. Es geht also in diesem Fall nicht darum zu zeigen, dass eine Sprache nicht regulär ist sondern nur anzugeben wie diese pumpbar ist, doch da scheitert es bei mir.

Ich hoffe auf eure Hilfe Augenzwinkern

Meine Ideen:
Das einzige was ich bisher dazusteuern kann ist folgendes:

Die Sprache akzeptiert alle Worte die "aba" als Teilwort enthalten. Das bedeutet es können unendliche viele as und bs vor dem Wort und nach dem Wort stehen. Wir haben also keine Schleife in der Mitte, sondern am Anfang und am Ende eine.

Aber wie genau komme ich jetzt an eine Zerlegung, die die 3 Bedingungen erfüllt, welche das Pumping Lemma aufstellt.

07.11.2012, 23:02

Abakus

Auf diesen Beitrag antworten »

RE: Pumping Lemma
Hallo,

vielleicht suchst du das erste Vorkommen von aba. Dann kannst du mit dem aba (oder dem ba oder einem beliebigem Buchstaben vorher?) Potenzen bilden (ggf. Fallunterscheidung). Es wäre zu testen, wie weit diese Idee reicht?

Abakus smile

19.09.2013, 00:03

jimmyt

Auf diesen Beitrag antworten »

RE: Pumping Lemma

Zitat:

Original von Shaggz
... Findet man eine Zerlegung, die nicht von der Sprache akzeptiert wird, hat man gezeigt, dass die Sprache nicht regulär ist. ...

Das stimmt so nicht. Wenn es eine Zerlegung $\begin{eqnarray*} z=uvw \end{eqnarray*}$ mit $\begin{eqnarray*} |z| \ge n \end{eqnarray*}$ für ein beliebiges $\begin{eqnarray*} n \in N_0 \end{eqnarray*}$ gibt, für die das Pumping Lemma funktioniert, dann ist die Sprache regulär. Ganz gleich, ob es noch eine oder auch mehrere Zerlegungen gibt, für die das PL nicht funktioniert.

Beispiel:
Die Sprache $\begin{eqnarray*} L=a^nb^m \end{eqnarray*}$ ist regulär. Trotzdem gibt es eine Zerlegung mit $\begin{eqnarray*} v=ab \end{eqnarray*}$ die durch das Pumpen Wörter generiert, die nicht in der Sprache sind. Aber es gibt eine andere Zerlegung mit bspw. $\begin{eqnarray*} v=a \end{eqnarray*}$ die durch das Pumpen Wörter erzeugt die in der Sprache sind.

Du musst also eine Zerlegung finden, für die das PL funktioniert und nicht eine Zerlegung für die es nicht funktioniert.
Erst wenn du gezeigt hast, dass es überhaupt keine Zerlegung gibt, für die das PL funktioniert, erst dann ist die Sprache nicht regulär.

19.09.2013, 00:18

jimmyt

Auf diesen Beitrag antworten »

RE: Pumping Lemma

Zitat:

Original von Shaggz
... So nun ist meine Aufgabe explizit anzugeben, wie die Sprache die alle Wörter mit "aba" (Das Alphabet besteht nur aus a´s und b´s) als Teilwort akzeptiert, pumpbar ist. ...

Also $\begin{eqnarray*} L=(a|b)^*(aba)(a|b)^* \end{eqnarray*}$ . Wie wäre es mit $\begin{eqnarray*} v=aba \end{eqnarray*}$ ?
Und dann die Fälle durchgehen für $\begin{eqnarray*} u=\epsilon \end{eqnarray*}$ , $\begin{eqnarray*} u=(a|b)^* \end{eqnarray*}$ und $\begin{eqnarray*} u=(a|b)^*(aba) \end{eqnarray*}$ für die Wörter $\begin{eqnarray*} z=uv^iw \end{eqnarray*}$ .

19.09.2013, 07:47

Iorek

Auf diesen Beitrag antworten »

Ob sich der Fragesteller nach ca. 1 Jahr wirklich noch mal melden wird... verwirrt

19.09.2013, 10:54

jimmyt

Auf diesen Beitrag antworten »

@Iorek :

Ok, da hast du natürlich recht. Ich habe nicht auf's Erstellungsdatum geachtet. Augenzwinkern

Neue Frage »

Antworten »

Pumping Lemma

Verwandte Themen