Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten 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)

Beantwortet: Zusammenhang der kontextfreiensprache in Grammatik in Bezug zum PPL

Thu, 07 Feb 2019 20:51:56 +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)

Beantwortet: Reicht ein speziefisches Wort zur Widerlegung des Pumpinglemmas?

Thu, 26 Jan 2017 08:49:34 +0000

Hallo,
da hast du die Grundlegende Idee hinter dem PPL noch nicht so ganz verstanden. Wir versuchen ja beim PPL gerade durch die Verwendung der Hochzahlen zu zeigen, dass wir für ALLE n und für ALLE Zerlegungen des Wortes mindestens EINE mögliche Pumpvariable finden, bei der es zu einem Widerspruch kommt.
Also kannst du eben nicht nur ein mögliches Wort finden, sonder musst es für alle n zeigen. Jede EA-Sprache muss ja auch nur für EIN n EINE Zerlegung besitzen, für die wirklich alle Pumpmöglichkeiten noch Teil der Sprache sind. Schau dir am besten nochmal die Folie 29 im 2. Kapitel an da steht das ganz gut erklärt.
Ich hoffe das hat dir ein bisschen geholfen.

Beantwortet: Ausreichender Beweis

Sat, 14 Jan 2017 15:13:13 +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

Beantwortet: Definitionsbereiche von n bei PPL

Tue, 09 Feb 2016 17:29:42 +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.

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)

Beantwortet: alternative Argumentation: richtig?

Tue, 25 Nov 2014 09:40:47 +0000

Nein, diese Argumentation ist leider nicht zulässig, da |xy| jede Anzahl kleiner gleich n (≤n) annehmen kann, du allerdings in deiner Argumentation die (exakte) Gleicheit voraussetzt.

Dadurch entstehen übrigens weitere Fehler bei dir, also bitte gleich Zeile 2 ändern und dann nochmal von vorne ;)

Gruß

Philip (Tutor)

Beantwortet: Ist Widerspruchsbeweis durch definieren von xy & z zulässig?

Tue, 25 Nov 2014 09:27:42 +0000

Hallo,

ich verstehe leider nicht ganz, wie man am Ende auf $z = 0^{n-k}1^n$ kommt.

Weil man nimmt doch den Fall an, dass $i=0$ ist. Also $w' = xy^0z$

Demnach hätte ich gedacht, dass $y^0 = 1$ ist, also man dann da stehen hat:

x1z=0^{j-k}10^{n-j}1^n=0^{n-k}1(n+1)

Wo liegt mein Denkfehler?

Danke

Beantwortet: PPL für jede Zerlegung ?

Tue, 25 Nov 2014 09:13:59 +0000

Hallo Adam, hallo Sven,

Adam hat trotzdem mit seiner Anmerkung recht - wir haben das nicht hundertprozentig korrekt formuliert. Wir werden das ändern zu:

"Es seien $x,y,z∈E^∗$ Wörter, sodass gilt: $w=xyz$ und [...] (1), (2), (3)"

(oder so ähnlich).

Viele Grüße

Lukas König