Minimal notwendige/r Begründung/Widerspruch

Question

Hallo,

wenn ich meine Widersprüche bei Aufgaben zum kontextfreien PPL hauptsächlich informel (nicht mathematisch sondern "verbal") führe, ist meine Frage, was da der minimale Umfang sein muss. Dies ist eine generelle Frage, lässt sich aber gut an PUM-AH veranschaulichen, ist aber zum Beispiel auch bei der Lösung von PUM-AI relevant.

Ich habe als mögliche Pumpstellen identifiziert:
$vx \in\{a\},\{b\},\{a,b\}$

Für $vx \in \{a\},\{b\}$ ist die Begründung ja logisch.

Für $vx \in \{a,b\}$ frage ich mich jedoch, ob die Fallunterscheidung notwendig ist oder nicht mit dem ersten Teil der Begründung auch der zweite Teil ad absurdum geführt wurde und die dort gelieferte Begründung nurnoch ein zusätzliches Ausschlusskriterium bildet.

Selbiges gilt für beide Fallunterscheidungen in Aufgabe PUM-AI.
Da maximal Elemente aus 2 der 3 Klammern gepumpt wederden können, wird zwangsläufig das Verhältnis der Klammer-Terme untereinander gestört.
Die Fallunterscheidung im Ersten Fall könnte also auch in einem Satz formuliert und die zweite Fallunterscheidung ganz weg gelassen werden, da zwar ein Zeichen doppelt vorkommt aber auch das Verhältnis der drei Terme gestört wird (was ja schon erwähnt wurde).

Also zusammenfassend: Reicht es aus einen generellen Gegenbeweis in einem wohlformulierten Satz zu führen, ohne mögliche weitreichendere Verstöße gegen die Definition der Sprache zu behandeln, da diese ja implizit sind?

Besten Dank und ich hoffe ich habe mich verständlich ausgedrückt.

Comments

Also: Da Sie von der Möglichkeit sprechen, verbal (im Gegensatz zu math. formal) auf Fragen zu antworten, muss erst einmal generell festgestellt werden, dass dann großer Wert auf präzise Formulierungen gelegt werden muss. Verbal zu antworten, ist kein Problem, aber dann muss auch das, was dasteht, eindeutig ihre Idee beschreiben und es mössen alle notwendigen Fälle abgedeckt sein, genau so, wie das bei einer formalen Beschreibung auch der Fall wäre.

Bei Ihrer Formulierung oben höre ich (jetzt mal demonstrativ) auf zu lesen, wenn Sie schreiben "Ich habe als mögliche Pumpstellen identifiziert: $vx \in \{a\},\{b\},\{a,b\}$." Dabei sind mehrere Dinge falsch - im Sinne von "nicht ganz korrekt", nicht unbedingt im Sinne von "keine Punkte", aber lassen Sie uns das zur Verdeutlichung einmal ganz streng durchexerzieren.

Zunächst können Sie bei der normalen Anwendung des PPL, wo wir auf die Gegenaussage hinauswollen, nicht "die Pumpstelle identifizieren". Die Pumpstelle ist Ihnen als Beweisführendem unbekannt, Sie müssen über alle möglichen Pumpstellen argumentieren. Es gibt natürlich "Klassen von ähnlichen Pumpstellen", und darauf wollen Sie hier hinaus - aber dann schreiben Sie das auch so, damit wir sehen, dass Sie die Idee des PPLs verstanden haben. Außerdem schreiben Sie irgendwas von $vx \in \{a\},\{b\},\{a,b\}$, und als Mathematiker - die wir alle in unserer Funktion als Info-II-Betreuer sind - wird uns dann erstmal ganz schummrig :-) Sie dürfen verbale Antworten geben, aber achten Sie darauf, so präzise wie möglich zu sein und umgekehrt möglichst wenig Spielraum für Fehldeutungen zu lassen.

Mein Vorschlag: Versuchen Sie Ihren Text nochmal so zu überarbeiten, dass er eine gültige Beweisführung für eine der beiden Aufgaben darstellt, und dann schaue ich wieder drüber. Wenn Sie das gut machen, mag eine Fallunterscheidung vielleicht tatsächlich überflüssig werden.

---

Das ist übrigens eine wichtige Frage, danke, dass Sie sie gestellt haben!

---

Vielen Dank für Ihre Antwort.

Ich sehe ein, dass meine Formulierung in der Frage nicht vollkommen korrekt ist. Ich habe versucht den Fall möglichst kurz darzustellen, um den Kern der Aussage zu skizzieren.

Ich versuche nochmal eine "verbale" Begründung zu liefern, wie ich sie auch gerne in einer Klausur verwenden würde.

Es geht weiterhin um Aufg. PUM-AH.
Ich gehe der Einfachheit halber davon aus, dass ich die Bedingungen und das Testwort schon richtig aufgestellt habe.

Als mögliche Belegungen für die Worte v und x habe ich gefunden, dass diese entweder nur a's, nur b's oder sowohl a's als auch b's enthalten.

Für den Fall, dass nur a's oder b's in $ v $ und $ x $ enthalten sind, führt ein pumpen mit $ i\neq1 $ zu einer einseitigen Verschiebung des Verhältnisses zwischen $ a $'s und $b$'s. In Folge ist $ z \notin L $.

Für den Fall, dass $v$ und  $x$ sowohl $a$'s als auch $b$'s in einer beliebigen Belegung enthalten führt ein pumpen von $v$ und $x$ mit $i=0$ zu einer Veränderung in der Anzahl der $a$'s und innerhalber der ersten k $b$'s. Da die Anzahl der $b$'s jedoch $k*k$ betragen soll führt eine Veränderung des ersten $k$'s bei zwangsläufig gleichbleibendem zweiten k und einer gleichzeitige Änderung der $a$'s zu einem Ungleichgewicht im Verhältnis der $a$'s und $b$'s und somit zu $ z \notin L $.

In meinem Verständnis sollte ich so gezeigt haben, dass L nicht kontextfrei ist. Würde das so akzeptiert oder ist das zu ungenau oder habe ich möglicherweise irgendwo einen Denkfehler gemacht?

Vielen Dank für Ihre Hilfe

---

So haben Sie das wirklich gut formuliert! Für eine Klausur wäre das absolut in Ordnung. Formaler würden wir das sicher nicht erwarten. (Ich nehme übrigens auch angetan zur Kenntnis, dass Sie Latex in Ihren Formeln verwendet haben. Prima!)

Ich bin allerdings bei der Begrüdung nicht ganz einverstanden. Enthält $vx$ sowohl $a$'s als auch $b$'s, dann gilt also irgendwie $vx=a^nb^m$. In diesem Fall müssen wir unterscheiden, wo die Grenze verläuft. Enthält $v$ oder $x$ sowohl $a$'s als auch $b$'s, ist es einfach, denn dann wird die Struktur der Sprache $L$ beim Pumpen durchbrochen. Der Fall $v=a^n$ und $x=b^m$ ist allerdings komplizierter, denn wir wissen nicht, wie groß $m$ und $n$ sind. Vielleicht führt das Pumpen ja zufällig wieder auf ein korrektes Wort. Ein zunächst denkbares (aber natürlich unmögliches - sonst wäre unsere Begründung im Buch falsch) Beispiel wäre, dass wir etwa das Wort $$aabbbb$$ haben, dann irgendwie $v=a^2$, $x=b^8$ gilt (also mehr $b$'s als überhaupt im Wort vorkommen; das ist komplett gegen die drei Bedingungen des PPL, aber sei es nur für einen Augenblick als Gedankenexperiment so zugelassen), außerdem sei $uwy=\lambda$ und nach dem Pumpen mit $2$ würde dann gelten: $uv^iwx^iy = v^2x^2=a^4b^{16} \in L$.

Das GILT in diesem Fall absolut nicht, ich habe ja Wörter verwendet, die nicht den drei Bedingungen des PPL entsprechen! Aber Sie müssen zeigen, dass es auch in allen anderen Fällen nicht gelten kann. Dafür ist der schwierigste der drei Fälle aus dem Buch da. Wir müssen für alle denkbaren Zerlegungen zeigen, dass das Pumpen dazu führt, dass wir aus der Sprache fallen. Dafür müssen wir auch in den abstrusesten Fällen sicherstellen, dass wir nicht "zufällig" doch wieder auf einem Wort aus der Sprache landen.

Dazu muss ich aber noch eine Bemerkung hinterherschieben: Gerade wegen dieses dritten schwierigen Falls ist die Aufgabe PUM-AH deutlich über Klausurniveau! Begründungen in der Art, wie Sie sie hier geliefert haben, sollten in der Klausur locker ausreichen.

---

Vielen Dank für diese sehr aufschlussreiche Antwort!

Diesen Sonderfall habe ich wirklich nicht bedacht, da ich dachte, dass man sich auf die möglichen Kombinationen aus dem Testwort beschränken kann. Das dies nicht der Fall ist/sein muss, ist eine sehr wichtige Erkenntnis und ich bin umso froher, dass eine Aufgabe mit einem solchen Umfang in einer Klausur eher weniger zu erwarten ist.

Die LaTeX Implementierung ist durchaus sehr praktisch, jedoch wäre ich ohne die umfangreiche "Bearbeiten" Funktion aufgeschmissen gewesen.

---

Auch in den einfacheren Fällen, die in einer Klausur auftauchen können, muss man allerdings immer überlegen, ob man auch wirklich nicht nach dem Pumpen auf einem (anderen) Wort der Sprache landen könnte.