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

Minimal notwendige/r Begründung/Widerspruch

Wed, 11 Jan 2017 23:46:08 +0000

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.

Beantwortet: alternativer Beweis

Wed, 04 Jan 2017 19:18:04 +0000

Ich gehe mal davon aus, dass du von Wort $w=a^kb^{k^2}$ und $i=2$ ausgehst.

Dann ist deine Aussage "für jedes gepumpte a muss zusätzlich k b's entstehen" falsch. Beispiel: $w=a^2b^4$ ->k=2 -> gepumptes Wort $a^3b^9$ -> es müssen 5 b's entstehen und nicht 2

Für ein gepumptes a müssen zusätzlich $2k+1$ b's entstehen, für zwei gepumpte a's müssen zusätzlich $4k+4$ b's entstehen, für 3 müssen $6k+9$, ...

D.h. für jedes gepumpte a müssen mindestens $2k+1$ b's entstehen.

Jetzt kann man die Argumentation wie in Aufgabe 69 verwenden:

vx muss entweder leer sein -> Widerspruch
oder vx muss mindestens $2k+2$ Zeichen enthalten -> Widerspruch

Viele Grüße Philipp (Tutor)

Beantwortet: Alternativer Beweis

Thu, 11 Feb 2016 12:51:02 +0000

Hallo udeqy,

ja, meiner Meinung nach wäre diese Begründung auch korrekt!

Gruß,
Janine (Tutorin)