Pumping Lemma

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

1

Sunday, August 29th 2010, 11:49am

Hallo zusammen. Ich lerne gerade für die Theoretische Informatik Klausur und bin beim Pumping Lemma und komme nicht so ganz zurecht.

Hier mal was ich für Übungsblatt 5 so zusammenbekommen habe:

Aufgabe 1: L(2) = { a^k b^l a^k | k, l Element von N }

Man soll nun nachweisen, dass L(2) nicht durch einen endlichen Automaten entschieden werden kann (also nicht regulär ist?). Meine Lösung:

Angenommen, L(2) sei regulär. Dann gibt es ein x, dass wir in uvw zerlegen können, sodass die Eigenschaften des Pumping Lemmas gelten. Betrachte nun das Wort x = uvw = a^n b^m a^n. Dieses hat die Länge 2n + m.

Aus |v| >= 1 und |uv| <= n folgt, dass v nur aus a's besteht. (Da ja |a^n| = n)

Für uv²w würde dann aber gelten, dass vorne doppelt so viele a's wie hinten stehen, und solche Worte sind ja nicht in L(2).

Stimmt das so weit? Bei Aufgabe 2 stoße ich dann nämlich auf das Problem, dass ich heraus bekomme, dass das Pumping Lemma erfüllt ist, obwohl ich zeigen soll, dass die Sprache nicht regulär ist.

L = a^k b^l | k, l Element von N, k > l

Ich betrachte das Wort x = uvw = a^n b^m, |x| = n+m
Aus den ersten beiden Bedingungen des Pumping Lemmas folgt wieder, dass v nur aus a's besteht (wundert mich ein bisschen, dass ich das immer rausbekomme?). Nun liegen aber alle uv^i w, i >=0 in der Sprache, daes ja immer mehr a's als b's gibt, und solche Wörter definiert die Sprache ja gerade.

EDIT: Ist Latex kaputt?

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 2 times, last edit by "Skuld" (Aug 29th 2010, 11:52am)

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

2

Sunday, August 29th 2010, 1:17pm

Hi Skuld,

dein Wort x darf als Variable nur noch n im Exponenten haben. Bei Aufgabe 1 ändert sich aber nichts. Wählst Du zum Beispiel x = a^nba^n läuft der Rest genauso wie von Dir beschrieben.

Bei Aufgabe 2 solltest Du daran denken, daß man nicht nur "aufpumpen" kann, sondern auch "abpumpen" kann: uv^0w

Und als Beispiel-Wort für Aufgabe 2 wählst Du dann ein Wort, das gerade noch so die Bedingung k > l erfüllt und als Variable nur n in den Exponenten stehen hat (welches Wort wird das dann wohl sein ... ;-)) und zeigst dann, daß uv^0w nicht mehr zur Sprache gehört.

Viele Grüße
Carsten

Go to the top of the page

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

3

Sunday, August 29th 2010, 2:11pm

Wenn ich dich richtig verstanden habe, wähle ich also in Aufgabe 2 zB das Wort x = a^n b, aus den Bedingungen ergibt sich wieder, dass v nur aus a's besteht und für uv^0 w ergibt sich dann, dass das Wort nur aus "b" besteht, was aber nicht zur Sprache gehört - richtig?

Danke für die Hilfestellung, ich hoffe ich komme mit den restlichen Aufgaben besser klar

Ach, und noch mal zur Klarstellung: Die Aufgabenstellungen "Zeigen Sie, dass die Sprache nicht von einem endlichen Automaten entschieden werden kann" und "Zeigen Sie, dass die Sprache nicht regulär ist", sind äquivalent?

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 1 times, last edit by "Skuld" (Aug 29th 2010, 2:16pm)

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

4

Sunday, August 29th 2010, 2:26pm

nee, so geht das nicht. Bei beispielsweise u=a^(n-1) und v=a bekommst Du durch das abpumpen a^(n-1)b, was ja immer noch zur Sprache gehört.

Mit "gerade noch zur Sprache gehörend" meinte ich, daß sich k und l um genau 1 unterscheiden:

x = a^(n+1)b^n

Egal wie die a's nun auf u und v verteilt werden, es kommen durch das Abpumpen höchstens genauso viele a's wie b's geraus.

Quoted from "Skuld"

Ach, und noch mal zur Klarstellung: Die Aufgabenstellungen "Zeigen Sie, dass die Sprache nicht von einem endlichen Automaten entschieden werden kann" und "Zeigen Sie, dass die Sprache nicht regulär ist", sind äquivalent?

Ja.

Viele Grüße
Carsten

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

5

Sunday, August 29th 2010, 2:34pm

Kleine Ergänzung noch:

Quoted from "Skuld"

Für uv²w würde dann aber gelten, dass vorne doppelt so viele a's wie hinten stehen, und solche Worte sind ja nicht in L(2).

Das kann man so nicht sagen, da die a's beliebig auf u und v verteilt werden können. Bei u=a^(n-1) und v=a hätte uv^2w vorne genau ein a mehr als hinten, was aber natürlich ebenfalls nicht zur Sprache gehört. Sprich: In diesem Fall kann man nur sagen, daß vorne auf alle Fälle mehr a's sein werden als hinten, aber nicht wieviele mehr.

Viele Grüße
Carsten

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

6

Sunday, August 29th 2010, 4:34pm

Quoted from "Panoramix"

dein Wort x darf als Variable nur noch n im Exponenten haben.

Das ist so nicht ganz korrekt. Das Wort muss lediglich mindestens die Länge n haben. Wenn es --- wie Skuld geschrieben hat --- die Länge 2n+m hat, ist das auch okay. Bei den übrigen Bemerkungen und Tipps hast Du jedoch Recht Panoramix.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

7

Monday, August 30th 2010, 1:03pm

Eine Frage zu Aufgabenstellungen bei Kellerautomaten: "Geben Sie den KA an und begründen Sie seine Korrektheit!" -> d.h. für ein gültiges Beispielwort die Rechnung durchführen?

Ach und ist eine Überführung der Form z(1) # A -> z(2) gültig? D.h. ohne dass ich was aus dem Keller lösche oder etwas in ihn hineinschreibe (also praktisch das gelesene Zeichen überlese?)

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 1 times, last edit by "Skuld" (Aug 30th 2010, 1:05pm)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

8

Monday, August 30th 2010, 3:24pm

Quoted from "Skuld"

Eine Frage zu Aufgabenstellungen bei Kellerautomaten: "Geben Sie den KA an und begründen Sie seine Korrektheit!" -> d.h. für ein gültiges Beispielwort die Rechnung durchführen?

Nein das reicht nicht aus. Angenommen es ist die Sprache L gegeben und nach einem KA gefragt. Dann musst begründen wieso der von Dir angegebene KA M alle Wörter von L erzeugt (L\subseteq L(M)), und dann noch begründen warum er auch keine zu viel erzeugt, die nicht in der Sprache sind (L(M)\subseteq L).

Quoted from "Skuld"

Ach und ist eine Überführung der Form z(1) # A -> z(2) gültig? D.h. ohne dass ich was aus dem Keller lösche oder etwas in ihn hineinschreibe (also praktisch das gelesene Zeichen überlese?)

Mir ist hier nicht ganz klar was Du mit "z(1) # A -> z(2)" meinst, da # i.d.R. ein Kellersymbol ist und die Übergangsfunktion als "Z x Sigma x Gamma -> Z x Gamma^*" definiert wird, wobei Z die Menge der Zustände, Sigma das Eingabe- und Gamma das Arbeitsalphabet ist.

PS: der LaTeX-Plugin scheint kaputt zu sein.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

9

Monday, August 30th 2010, 3:49pm

Quoted from "Arne"

Mir ist hier nicht ganz klar was Du mit "z(1) # A -> z(2)" meinst, da # i.d.R. ein Kellersymbol ist und die Übergangsfunktion als "Z x Sigma x Gamma -> Z x Gamma^*" definiert wird, wobei Z die Menge der Zustände, Sigma das Eingabe- und Gamma das Arbeitsalphabet ist.

PS: der LaTeX-Plugin scheint kaputt zu sein.

Ach ja, vergessen zu erwähnen: Das # ist hier tatsächlich Teil des Wortes (Aufgabenblatt 6, Aufgabe 1, L = {w#w^R}). Meine Frage ist, ob ein Übergang im Kellerautomaten erlaubt ist, der nichts in den Keller schreibt oder aus ihm löscht, sondern lediglich in einen neuen Zustand übergeht.

Ach, und wie zeige ich, dass der KA genau die Worte erzeugt? Durch erläutern des Vorgehens des Automaten, oder kann man das auf irgend eine Art formell zeigen?

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 1 times, last edit by "Skuld" (Aug 30th 2010, 3:51pm)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

10

Monday, August 30th 2010, 4:00pm

Dann schreib doch z(1) # A -> z(2) A. Dann wird weder was neues auf den Keller geschrieben, noch etwas altes gelöscht.

Du kannst formell aufschreiben welche Form die Wörter in welchem Zustand haben und dann schließlich zeigen inwiefern die Übergänge von einem in den anderen Zustand diese Eigenschaften verändern. Für Endzustände müsstest Du dann zeigen das diese Wörter genau die Eigenschaft der Wörter der gegebenen Sprache haben.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Schokoholic

Fritz

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

11

Monday, August 30th 2010, 9:09pm

$\LaTeX$ sollte nun wieder funktionieren... bitte entschuldigt die Unannehmlichkeiten.

Hier gibt es nützliche Links zum Studium

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

12

Monday, August 30th 2010, 9:14pm

Quoted from "Schokoholic"

$\LaTeX$ sollte nun wieder funktionieren... bitte entschuldigt die Unannehmlichkeiten.

Ja, funktioniert wieder. Danke!

Go to the top of the page

sebid

Junior Schreiberling

Posts: 168

Date of registration: Oct 5th 2004

Location: Hannover

13

Tuesday, August 31st 2010, 8:50am

Nochmal Pumping-Lemma

Aus der Klausur SS07.

Aufgabe 3:

Beweisen Sie, dass $L = \{a^{2n}b^{3n} |n \in \mathbb{N}\}$ nicht regulär ist.

Wie sieht hier das passende x und die Zerlegung uvw aus?
Ich steh da irgendwie auf dem Schlauch und bekomme keine passende Zerlegung hin.

Danke.

Cee Uhh!
:o) sebid

Go to the top of the page

SunshineSunny

Sonnenscheinchen auf'm Campus

Posts: 1,071

14

Tuesday, August 31st 2010, 10:06am

Nur so ne Idee von mir... wenn du das so umformst: $a^{\frac{2}{3} n} b^{n}$

Dann kannst du mit uv ein ganzes n nehmen also $\frac{2}{3}$ a's und $\frac{1}{3}$ b's

Aber keine Ahnung, ob das geht...

Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

15

Tuesday, August 31st 2010, 10:16am

Quoted from "sebid"

Aus der Klausur SS07.

Aufgabe 3:

Beweisen Sie, dass $L = \{a^{2n}b^{3n} |n \in \mathbb{N}\}$ nicht regulär ist.

Wie sieht hier das passende x und die Zerlegung uvw aus?
Ich steh da irgendwie auf dem Schlauch und bekomme keine passende Zerlegung hin.

Danke.

Deine Frage ist ein wenig irrführend formuliert. Du meinst wohl eher "Wie sieht hier das passende

aus und wie zeige ich für alle möglichen Zerlegungen

, dass für jede es ein

gibt, sodass das $uv^iw\notin L$ ?", oder?

Wie wärs, wenn du $x=a^{2n}b^{3n}$ wählst?

Also angenommen

ist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser

.

Für alle Zerlegungen

gilt nun, dass

nur aus

s und mindestens einem besteht (aufgrund der Anfangslänge). D.h. wenn wir nun beispielsweise

wählen, dann gilt nun: $uv^0w=uw=a^{2n-|v|}b^{3n}$ . Da jedoch $|v|\ge1$ ist, verletzt dies genau die Bedingung, dass alle Wörter die Form $a^{2n}b^{3n}$ haben sollen für die Anzahl der

s. Also gilt $uv\notin L$ , was ein Widerspruch zur Annahme ist.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

16

Tuesday, August 31st 2010, 10:17am

Quoted from "SunshineSunny"

Dann kannst du mit uv ein ganzes n nehmen also $\frac{2}{3}$ a's und $\frac{1}{3}$ b's

Verstehe ich nicht.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

SunshineSunny

Sonnenscheinchen auf'm Campus

Posts: 1,071

17

Tuesday, August 31st 2010, 10:27am

Hat sich auch erledigt... Deine Erklärung klingt logisch und einfacher

Hab irgendwie nicht im Blick gehabt, das es auch reicht keine 2n a's mehr zu haben...

Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Go to the top of the page

sebid

Junior Schreiberling

Posts: 168

Date of registration: Oct 5th 2004

Location: Hannover

18

Tuesday, August 31st 2010, 12:32pm

Quoted

Deine Frage ist ein wenig irrführend formuliert. Du meinst wohl eher "Wie sieht hier das passende aus und wie zeige ich für alle möglichen Zerlegungen , dass für jede es ein gibt, sodass das $uv^iw\notin L$ ?", oder?

Ja natürlich.

Quoted

Wie wärs, wenn du $x=a^{2n}b^{3n}$ wählst?

Hatte ich probiert, kam damit aber nicht weiter, da mein |uv| damit immer länger als n war.

Quoted

Also angenommen ist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser .

Für alle Zerlegungen gilt nun, dass nur aus s und mindestens einem besteht (aufgrund der Anfangslänge). D.h. wenn wir nun beispielsweise wählen, dann gilt nun: $uv^0w=uw=a^{2n-|v|}b^{3n}$ . Da jedoch $|v|\ge1$ ist, verletzt dies genau die Bedingung, dass alle Wörter die Form $a^{2n}b^{3n}$ haben sollen für die Anzahl der s. Also gilt $uv\notin L$ , was ein Widerspruch zur Annahme ist.

Ich verstehe die Stelle mit dem $uw=a^{2n-|v|}b^{3n}$ nicht.
Wo kommt dieses

her?

Danke.

Cee Uhh!
:o) sebid

Go to the top of the page

Sebastian

Trainee

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

19

Tuesday, August 31st 2010, 1:07pm

Quoted from "sebid"

Quoted

Also angenommen ist regulär, dann gilt PL mit den 3 Regeln, und insbesondere auch für unser .

Für alle Zerlegungen gilt nun, dass nur aus s und mindestens einem besteht (aufgrund der Anfangslänge). D.h. wenn wir nun beispielsweise wählen, dann gilt nun: $uv^0w=uw=a^{2n-|v|}b^{3n}$ . Da jedoch $|v|\ge1$ ist, verletzt dies genau die Bedingung, dass alle Wörter die Form $a^{2n}b^{3n}$ haben sollen für die Anzahl der s. Also gilt $uv\notin L$ , was ein Widerspruch zur Annahme ist.

Ich verstehe die Stelle mit dem $uw=a^{2n-|v|}b^{3n}$ nicht.
Wo kommt dieses her?

Danke.