Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in PUM-AA

Beantwortet: Pumping Lemma 2018-H-03

Tue, 09 Mar 2021 09:34:43 +0000

Hey uuuah,

das Wort geht selbstverständlich auch und mit i=0 liegt ist das Wort nicht mehr in der Menge, also hast du gezeigt, dass es keine rechtslineare Sprache ist.

Viele Grüße und viel Erfolg beim weiteren Lernen :)

Beantwortet: Pumping-Lemma Wortwahl

Mon, 10 Feb 2020 14:52:22 +0000

Hallo uoioh,

da das Pumping Lemma ein Widerspruchsbeweis ist, genügt es hier, einen möglichen Aufbau des Wortes zu verwenden und für diesen zu zeigen, dass die Bedingungen dafür nicht alle erfüllt sind. Hat man es für ein Wort bewiesen, ist der Widerspruch erfüllt.

Ich glaube, das mit dem Testen des einzigen Wortes hast du falsch verstanden. Es genügt uns, für ein Wort zu zeigen, dass alle möglichen Zerlegungen in x, y und z dazu führen, dass eine der drei Bedingungen (1), (2) oder (3) nicht erfüllt ist.

Ein Problem gibt es nur, wenn du ein Wort wählst, und die Bedingungen nach dem Pumpen zufällig immer noch alle korrekt sind. Das ist bei den Aufgaben im Normalfall aber nicht so.

Viele Grüße
Hannah (Tutorin)

Beantwortet: Kommt PPL für Kontextfreie Grammatik dran oder nicht?

Sat, 08 Feb 2020 10:36:00 +0000

Wurde schon mehrmals beantwortet - ja, es ist klausurrelevant!

Beantwortet: Pumping Lemma Beweisführung welche Sprachen ?

Sun, 05 Jan 2020 06:47:07 +0000

Hallo,

es gibt zwei Arten des Pumping Lemma. Eins für reguläre Sprachen und eins für kontextfreie Sprachen. Bisher habt ihr nur das für reguläre Sprachen kennengelernt. Das Semester ist aber noch nicht vorbei.

Viele Grüße

Niklas (Tutor)

Antwort ausgewählt: Zusammenhang der kontextfreiensprache in Grammatik in Bezug zum PPL

Sat, 09 Feb 2019 11:17:02 +0000

Hallo uzmzu,

mit dem PPL kannst du ja nur prüfen, ob eine Sprache nicht zu L1 (bzw. L3) gehört.
Es kann natürlich sein, dass du nur eine Pumpstelle bei deiner Sprache hast, es ist ja nur Vorrausgesetzt, das bei z = uvwxy, |z| >= n und die Pumpstellen v,x mit |vx| >= 1 sein (und der dritten Bedingung). Also kann v oder x auch lamda sein.

Und natürlich können die Pumpstellen auch unterschiedlich oft gepumpt werdem. Aber man kann sie auch gleich oft pumpen und das gepumpte Wort muss immer noch in der Sprache sein. Also nur ein spezieller Fall.

Dein Beispiel gehört zu L1, deshalb kann man mit dem PPL nicht zeigen, dass es nicht zur Sprache gehört

Es ist einfach nur das Vorgehen des PPL, dass es zwei Pumpstellen gibt, die gleich oft gepumpt werden. Deine angebrachten Punkte von dir sind für die Realisierung der individuellen Wörter des Sprache richtig.

Ich hoffe ich konnte dir weiterhelfen. Wenn es noch Unklarheiten gibt, schreibe einfach noch mal.

Viele Grüße

Anne (Tutor)

Beantwortet: Antwort Formulierung

Sun, 12 Feb 2017 12:49:11 +0000

Am besten du gehst das Pumping Lemma ganz formal durch. Mit allen Annahmen und Bedingungen. Falls du nicht weiterkommst kannst du auch deine Idee aufschreiben, wie du weiter vorgehen würdest. Das gibt mit Sicherheit nicht die volle Punktzahl, hilft uns aber deinen Gedankengang besser nachzuvollziehen.

Grüße, Felix (Tutor)

Kommentiert: Reicht ein speziefisches Wort zur Widerlegung des Pumpinglemmas?

Thu, 26 Jan 2017 09:17:11 +0000

Schauen Sie sich mal das entsprechende Kapitel im Lehrbuch an (ab Seite 207). Wir haben diesen Teil besonders ausführlich beschrieben, weil Studierende immer wieder Probleme mit dieser "umgekehrten" Argumentation beim PPL haben.

Das ist natürlich auch für die Klausur ein wichtiges Thema!

Antwort ausgewählt: Ausreichender Beweis

Sat, 14 Jan 2017 15:16:55 +0000

Na ja, fast. Ganz am Ende werden Sie ein bisschen schlampig mit den Bezeichnungen - $w$ ist oben gleich $0^n1^n$, da kann es unten nicht plötzlich $0^{n-k}1^n$ sein, zumindest, solange $k \geq 1$. Das können Sie stattdessen meinetwegen $w'$ nennen oder so.

Ansonsten ist der Beweis aber in Ordnung.

Beantwortet: Pumping-Lemma

Thu, 11 Feb 2016 09:55:02 +0000

Der Beweis muss korrekt sein. So allgemein, wie Sie das gerne hätten, kann man die Frage nicht beantworten. Machen Sie mal ein Beispiel, dann können wir darüber diskutieren, ob es korrekt ist.

(Erfahrungsgemäß machen es sich Studenten, die so, wie es Ihre Frage andeutet, an Beweisverfahren herangehen, eher zu einfach. Ein Beweis muss lückenlos sein, da gibt es keine Kompromisse. Das heißt nicht, dass es sehr viel Text sein muss, es muss auch nicht alles formal aufgeschrieben werden - aber es muss präzise dargelegt werden, warum das Pumpen in dem jew. Fall nicht möglich ist.)

Viele Grüße

Lukas König

Antwort ausgewählt: Definitionsbereiche von n bei PPL

Tue, 09 Feb 2016 17:31:00 +0000

Es handelt sich bei beiden PPLs um große $n$ (vor allem um mit dem gewählten Automaten oder der gewählten Grammatik wachsende $n$) - ob die 0 dabei ist oder nicht ist völlig irrelevant.

Im Fall von EA muss das $n$ mindestens so groß sein wie die Anzahl der Zustände eines EA - EAs mit $0$ Zuständen wären nicht einmal theoretisch wohldefiniert. Bei Grammatiken wächst das $n$ sogar exponentiell mit der Anzahl der Nonterminale - und auch hier darf es nicht $0$ Nonterminale geben.

Bearbeitet: PPL für jede Zerlegung ?

Tue, 25 Nov 2014 09:55:32 +0000

EDIT: Der folgende Beitrag bezieht sich auf eine veraltete Version des Pools; er wird trotzdem nicht zensiert, damit die Diskussion in diesem Thread verständlich bleibt.

Hallo,

die Beweisstruktur in diesem Beweis ist nicht korrekt! Es wird etwas falsches gefolgert:

"...Jetzt sei w=xyz beliebige Partition von w. Dann gilt laut PPL:

1) |xy|≤n

2) |y|>0

3)...

Diese Folgerung ist doch falsch. Das PPL sagt nämlich, dass es eine Partition gibt, sodass 1-3 gilt. Also insbesondere, dass es nicht für eine beliebige Partition gilt! Sonst müsste es im PPL heißen, dass dies für jede(!) Zerlegung gilt.

lg Adam

Beantwortet: PPL zum Nachweis regulärer Sprachen geeignet?

Tue, 25 Nov 2014 09:54:45 +0000

Hallo,

Ich verstehe nicht ganz, was du mit "das PPL ist erfüllt" meinst...Meinst du damit, dass die Aussagen (1)-(3) usw. erfüllt sind?

Das PPL ist nur ein Werkzeug, das besagt, welche Eigenschaften eine reguläre Sprache hat. Diese direkt nachzuweisen ist schier unmöglich, denn du müsstest dazu (1)-(3) usw. für ALLE Wörter nachweisen. Deswegen verwenden wir das PPL immer nur, um zu zeigen, dass eine Sprache nicht regulär ist. Für den Beweis, dass eine Sprache regulär ist, ist das PPL gänzlich ungeeignet.

In dieser Aufgabe ist w dein gewähltes Ausgangswort, das du durch Pumpen mit i so verändern möchtest, dass das daraus resultierende Wort nicht mehr in der Sprache drin liegt. Wenn du irgendwie ein anderes Ausgangswort pumpst und dann auf w als Ergebnis kommst, dann kannst du keine Aussage treffen. In sofern stimmt also deine 2. Vermutung.

Ich hoffe, das hat ein wenig weitergeholfen :)

Viele Grüße,

Vivian (Tutor)

Kommentiert: alternative Argumentation: richtig?

Tue, 25 Nov 2014 09:50:20 +0000

Nein, du kannst doch $p=j-1$ wählen, dann ist

$p=j-1 < j$ und $|y|= j-p = j-(j-1) = 1$.

Gruß,

Adam (Tutor)

Antwort ausgewählt: Ist Widerspruchsbeweis durch definieren von xy & z zulässig?

Tue, 25 Nov 2014 09:37:12 +0000

Nein, wenn du $w = 0^n1^n$ wählst, darfst du hier nicht die Einsen als xy und die Nullen als z definieren, da $w=xyz$ sein soll (hier wird also eine Reihenfolge von x,y und z bestimmt). Da $|xy|\leq n$ (1) kann xy nur aus 0 bestehen und z demzufolge nur aus 1.

Sven (Tutor)