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

Beantwortet: Pumping Lemma für kontextfreie Sprachen Aufgabe 65

Thu, 09 Feb 2017 14:04:25 +0000

Sie haben absolut recht! Das ist zwar kein Widerspruch und strenggenommen auch nicht im mathematischen Sinne falsch (denn man kann über zwei Einsen (oder auch vier oder fünf) im Wort sprechen, auch wenn das gar nicht möglich ist, solange sich keine logische Inkonsistenz ergibt), aber natürlich ist das überflüssig, und wir haben uns da offensichtlich verformuliert.

Vielen Dank für den Hinweis! Ich werde das in der Online-Version gleich anpassen. Wir hatten schon lange keinen neuen Fehler mehr in den Übungsbüchern - Sie haben ein gutes Auge!

Beantwortet: Alternative Lösung

Mon, 16 Jan 2017 10:56:47 +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)

Beantwortet: Verständnisfrage

Sat, 14 Jan 2017 17:25:20 +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)

Beantwortet: Verständnis Nr 65

Tue, 02 Feb 2016 16:25:49 +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)

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

Beantwortet: Vorgehensweise bei PPL für kontextfreie Sprachen

Tue, 25 Nov 2014 08:05:02 +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: alternative argumentation auch richtig?

Tue, 25 Nov 2014 07:57:47 +0000

Das allein würde nicht reichen. Sie müssen beim PPL immer formal korrekt argumentieren. Im Prinzip nutzen Sie Ihre Argumentation ja auch, indem Sie zeigen, wie man pumpen muss, um aus der Sprache zu fliegen. Es reicht aber nicht, das so schwammig hinzuschreiben.

Viele Grüße

Lukas König