Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zu Blatt 4 Aufgabe 3a
Verstehe ich vielleicht die Aufgabenstellung falsch? Es soll doch gezeigt werden, dass alle Zeichenketten der Form BKKK…KB, wobei zwischen dem linken und rechten B nur K stehen und davon mindestens 2, herleitbar sind. Oder verstehe ich das falsch? BKKB lässt sich ganz einfach ableiten. BKKKB bereitet mir gerade Schwierigkeiten und ich würde sogar behaupten, das ist unmöglich.
Notation: Bananen = B, Kirschen = K, alle anderen verwendeten Großbuchstaben stellen Zeichenketten (evtl = leer) dar.
Hat es jemand geschafft die Zeichenkette BKKKB herzuleiten oder findet jemand einen Fehler in meiner Argumentation? Der Induktionsschluss ist ja dann einfach. Aber der Start für n=3 irgendwie nicht.
Behauptung: Die Zeichenfolge BKKKB lässt sich nicht herleiten.
Beweis (durch Widerspruch): Annahme es gibt eine Herleitung für BKKKB. Dann gibt es auch eine kürzeste Herleitung (bezogen auf die Anzahl der Schritte). Eine solche kürzest mögliche Herleitung sei also gegeben. Irgendwo in der Herleitung von BKKKB
|_
|K
|.
|.
|.
|. 1. mal Regel (iii)
|.
|.
|.
BKKKKB
würde zum 1. mal Regel (iii) benutzt und zwei Zeichenketten XB, BY “verschmolzen” zu XY (es ist offensichtlich, dass es ohne Anwendung von Regel (iii) keine Chance gibt, BKKKB herzuleiten). Schauen wir uns diese Zeichenketten genauer an. Da jede Zeichenkette (außer der “leeren”, die ab jetzt mit “e” bezeichnet sei) mindestens ein K enthält, muss sowohl X, als auch Y ein K enthalten, also X=UKV und Y=U’KV’, wobei U,U’,V,V’ Zeichenketten (evtl=e) sind. Wäre in V oder in U’ ein B enthalten, würde beim Verschmelzen folgende Struktur entstehen XY=[…]K[…]B[…]K[…]. Da sich K nicht löschen lassen, wäre diese Zeichenkette unbrauchbar um BKKKB abzuleiten (das B zwischen den beiden K bekommt man nicht mehr weg). Folglich wäre der Schritt überflüssig im Widerspruch dazu, dass die Herleitung bzgl. der Anzahl der Schritte minimal ist. Folglich enthalten V und U’ kein B! Das bedeutet X und Y haben die folgende Struktur X=RK und Y=KS, mit (erstmal) unbekannten Zeichenketten R und S.
Offensichtlich führen R=e oder R=B zu einem Widerspruch (in beiden Fällen wäre BKB ableitbar, im Widerspruch zur Aufgabe b), die nämlich korrekt ist). Folglich enthält R ein K, also R=R’KR’‘. Offenbar darf R’’ kein B enthalten, denn sonst hätte X wieder K[…]B[…]K als Teilstruktur und X ließe sich nicht zur Herleitung von BKKKB verwenden (im Widerspruch zur kürzesten Herleitung). Folglich gilt R=TK, wobei T eine zunächst unbekannte Zeichenkette ist (tatsächlich ist auch T ohne K, also entweder leer oder sie besteht aus einer endlichen Anzahl von B; aber das ist an dieser Stelle irrelevant).
Schauen wir uns nun Y=KS an. In S kann ebenfalls kein K mehr vorkommen (sonst können nicht sowohl XB, als auch BY an der Herleitung von BKKKB beteiligt sein, im Widerspruch zur kürzesten Herleitung). Nun kann BY=BKS aber nur durch Regel (i) und (ii) hergeleitet worden sein (da die Zeichenfolge nur ein K enthält), folglich S=e. Damit folgt XY=TKKK. Dieser Term muss aber an der Herleitung von BKKKB beteiligt sein (wieder wegen der kürzesten Herleitung). Aus TKKK lässt sich aber nicht BKKKB ableiten, denn ein B hinter den 3 K ließe sich nur mittels Regel (iv) herleiten, allerdings würde dies ein 4tes K ins Spiel bringen. Widerspruch! Folglich ist die Annahme falsch.
Es ging von manchen Tutoren eine E-mail rum. Die Teilaufgabe enthält in ihrer Aufgabenstellung einen Fehler.
Es reicht aus, den Induktionsanfang für n=2 zu zeigen. Beim Induktionsschritt soll dann davon ausgegangen werden, dass dieser auch für n=3 gelte.
Danke für die Info. Habe gerade nachgeschaut. In einer Mail, in der um die Lösungen zu den Coq-Präsenzaufgaben ging (die ich deswegen noch nicht gelesen hatte), steht es am Ende in einer Bemerkung. :rolleyes:
(Unterstreichung von mir)
Das ist dann aber trotzdem eine seltsame Vorgehensweise, da die Behauptung für n=3 ja nun falsch ist (siehe oben).