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

Beantwortet: Verständnisfrage PUM-AD

Mon, 03 Feb 2020 08:10:01 +0000

Das frage ich mich auch. Es können doch garnicht beide Einsen vorkommen, da die Menge von der mittleren 0 = l ist und somit vwx entweder ganz oder teilweise (dann mit jeweils einer 1) enthält, aber nicht darüber hinaus. Daher kann vwx doch nur max eine 1 enthalten.

Somit können doch auch garnicht die Nullen aus allen drei Bereichen vorkommen, oder liege ich da komplett falsch.

Danke für die Rückmeldung,

Gruß

Kommentiert: Pumping Lemma für kontextfreie Sprachen Aufgabe 65

Thu, 09 Feb 2017 14:30:50 +0000

Bitte!

Ich habe eine neue Version hochgeladen und auch in der Errata darauf verwiesen: https://ilias.studium.kit.edu/goto.php?target=frm_130906_36313&client_id=produktiv

Antwort bearbeitet: Alternative Lösung

Mon, 16 Jan 2017 12:13:45 +0000

Ja, da du alle Zerlegungen mit deinen Fällen abdeckst.

Es hat sich noch ein Flüchtigkeitsfehler in deinem zweiten Fall eingeschlichen. Es müsste heißen: wegen |vwx|<=k kann ....

Viele Grüße

Philipp (Tutor)

Antwort ausgewählt: Verständnisfrage

Sun, 15 Jan 2017 08:25:58 +0000

Der 2.2 Fall wurde als "Mindestens eine Eins ist in vx enthalten" formuliert, da es komplementär zu "Keine Eins ist in vx enthalten" ist. Aber du hast Recht, man könnte auch schreiben "vx enthält eine Eins" und würde trotzdem alle Fälle abdecken, da vwx nur eine Eins beinhalten kann.

Zu deiner zweiten Frage: Man kann nicht immer im 2.2 Fall über die Anzahl der Nullen argumentieren, da z.B. $vx =1$ sein könnte, also vx aus keinen Nullen besteht. Wenn wir jetzt pumpen, ändert sich die Anzahl der Nullen nicht. Folglich können wir auch nicht über die Nullen argumentieren, dass das gepumpte Wort nicht mehr Teil der Sprache ist.

Viele Grüße

Philipp (Tutor)

Antwort ausgewählt: Verständnis Nr 65

Tue, 02 Feb 2016 17:17:41 +0000

Hallo,

das wäre hier natürlich ebenfalls richtig. Die Ausdrücke |vx| >= 1, |vx| > 0, vx != λ sind equivalent, da Wörter ja immer nur eine ganzzahlige Länge haben können.
Für die Variation kann ich keinen Grund erkennen, allenfalls um die verschiedenen Varianten aufzuzeigen.

Grüße,
Lukas (Tutor)

Beantwortet: Alternative Lösung: Schema wie bei EA

Tue, 25 Nov 2014 08:18:41 +0000

Die Idee mit dem Widerspruchsbeweis ist richtig, aber einfach das Verfahren vom Pumpinglemma für reguläre Sprachen abschreiben, geht nicht (selbst bei einer regulären Sprache wäre dein Beweis etwas lückenhaft). Dein Beweis sehr unvollständig und logisch alles andere als zwingend, gravierende Probleme sind u.a..:

- aus (1) und (2) kannst du nicht folgern, dass u=0^k . Es kann auch |u| > n gelten! --> vwx kann irgendwo im Wort sein. Für die Klausur wäre es auch gut, aufzuschreiben, was (1) und (2) überhaupt aussagt.

- warum ist das in der letzten Zeile ein Widerspruch?? und zu was? was folgt daraus?

Daher braucht man, wie in den anderen Beiträgen angesprochen, eine Fallunterschiedung, wo die Pumpstellen sind. Da hast nur den Fall, dass vwx innerhalb der ersten nullen liegt, betrachtet, und so getan, als ob das alle Fälle wären.

Die Lösung ist sehr ausführlich formuliert, aber es sind für einen korrekten Beweis ALLE angesprochenen Fälle nötig (siehe Kommentare der Übungsleiter).

Also: orientiere dich lieber an der Lösung zu dieser Aufgabe und den anderen Aufgaben zu diesem Thema als am Pumpinglemma für reguläre Sprachen.

Tobias (Tutor)

Erneut getaggt: alternative argumentation auch richtig?

Tue, 25 Nov 2014 08:15:27 +0000

Könnte man auch damit argumentieren, dass man, um die Struktur des gewählten Wortes "0^n 1 0^n 1 0^n" beim Pumpen zu beizubehalten, 3 Pumstellen benötigen würde (nämlich in den 0-er-Blöcken)? Da im PPL nur 2 Pumpstellen existieren würde dies zu einem Widerspruch führen...

Antwort ausgewählt: Vorgehensweise bei PPL für kontextfreie Sprachen

Tue, 25 Nov 2014 08:14:21 +0000

Die Vorgehensweise beim PPL für reguläre Sprachen bzw. beim PPL für kontextfreie Sprachen ist eigentlich vom Prinzip her sehr ähnlich. Ich erkläre das hier kurz am Beispiel des PPL für kontextfreie Sprachen.

Wenn eine Sprache kontextfrei ist, dann existiert eine Zahl $k∈N_0$ bei der für alle Wörter z in L mit $|z| \geq k$ eine Zerlegung $z = uvwzy$ existiert, für die gilt

(1) $|vwx| \leq k$

(2)$vx ≠λ$

(3) für alle $i∈N_0:uv^iwx^iy∈L$

Wenn Sie jetzt zeigen wollen, dass eine Sprache das PPL nicht erfüllt, dann müssen Sie diese Annahmen also widerlegen (wichtig werden jetzt die oben unterstrichenen Quantoren):

Also müssen sie für ein Wort z (beim PPL gilt es für alle) und alle hier möglichen Zerlegungen (vgl. oben es existiert eine Zerlegung), die die Bedingungen (1) und (2) erfüllen, zeigen, dass es mindestens ein i gibt (beim PPL für alle i) für welches $<span>i \in N_0: uv^iwx^iy \notin L$. Wenn Sie dies gezeigt haben, dann ist das ein Widerspruch zur Aussage des PPL und die Sprache ist nicht kontextfrei.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Beantwortet: Müssen generell alle 3 Fälle widerlegt werden?

Tue, 25 Nov 2014 08:14:15 +0000

Sie brauchen alle Fälle, da Sie es ja für alle Zerlegungen zeigen müssen (vgl. Sie hierzu: Vorgehensweise bei PPL für kontextfreie Sprachen ).

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König