Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in PUM-AI

Beantwortet: Pumpvariable wählen

Sun, 29 Jan 2017 23:33:34 +0000

Hallo,

die Pumpvariable i ist generell frei wählbar. Man muss schlichtweg für jede mögliche Zerlegung z=uvwxy ein i finden, sodass uv^iwx^iz nicht Element der Sprache ist. In diesem Fall wurde i einfach für alle Zerlegungen gleich 0 gewählt.

Viele Grüße

Monika (Tutorin)

Beantwortet: Verständnis Nr 67 Pumping-Lemma

Tue, 02 Feb 2016 17:29:59 +0000

Hallo uodjt,

es gab schonmal eine Frage die auf Ähnliches abzielte:

http://info2.aifb.kit.edu/qa/index.php?qa=3586&qa_1=unterscheidung-i-0-und-i-2

Das wichtige ist, dass der Fall von der konkreten Sprache abhängt und es keine Einfache Regel, à la kommt dies nimm das gibt.

Mein Tipp ist, schau dir die Sprache an und die Zerlegung die du gewählt hast. Dann ist es häufig mit einfachen i's wie i=0 oder i=2 zu zeigen. Ein Patentrezept gibt es aber nicht.

Viel Erfolg,

Marvin (Tutor)

Beantwortet: Teil b): Begründung notwendig?

Tue, 18 Nov 2014 11:00:17 +0000

Hallo,

ja, das ist notwendig! Wir machen ja eine Einschränkung der Struktur von vwx (nämlich dass es aus (ab)*, (ca)*, (bc)*, d.h. vwx aus diesen Blöcken besteht). Aber wir müssen doch alle möglichen Zerlegungen betrachten. Das ist keine zusätzliche Begründung oder ähnliches, das ist eine Fallunterscheidung über die mögliche Form der zerlegung!

Ein Beispiel für ein vwx aus b) wäre vwx=aba. Das hat nicht die Form aus a), jedoch gibt es eine Zerlegung, sodass vwx=aba ist, undzwar wenn u das leere Wort ist und y=b (ab)^(n-2) (ca)^n (bc)^n.

Dann ist das Wort

z=uvwxy=abab(ab)^(n-2) (ca)^n (bc)^n=(ab)^n (ca)^n (bc)^n,

und unsere Zerlegung erfüllt die Voraussetzungen!

Gruß,

Adam (Tutor)

Beantwortet: Pumping Lemmata: Begründung durch Worte oder mathematische Terme?

Tue, 18 Nov 2014 10:58:51 +0000

Kurze offizielle Stellungsnahme hierzu:

Beim Pumping Lemma für reguläre Sprachen haben wir es eigentlich immer formal korrekt angegeben, an diese Art sollten Sie sich hier gewöhnen.

Beim Pumping Lemma für kontextfreie Sprachen ist sowohl das eine als auch das andere möglich. Wichtig ist jedoch, dass es vollständig ist, d.h. auch für alle Zerlegungen gezeigt wurde.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König