Fallunterscheidung Pumping Lemma zur Widerlegung der dritten Regel

Question

Es gibt manchmal verschieden Möglichkeiten ein Wort aufzuteilen, z.B.

 

1) |vx| enthält mind ein a und kein c

2) |vx| entählt mind. ein c und kein a

 

müssen generell für den Widerspruch der dritten Regel (∀ i E No : w=xy^iz) alle Fälle bewiesen werden, oder reicht generell nur ein Besipiel bei dem es nicht funktioniert?? Genauso bei kontextrfreier Sprache.

Comments

So allgemein bzw. schwammig kann man das nicht beantworten. Können Sie etwas genauer formulieren, was Sie meinen? Was ist für Sie "ein Beispiel" und was sind "alle Fälle" - und was meinen Sie mit "kontextfreier Sprache"!? :-)

---

Das Beispiel bezieht sich sogar auf PPL für kontextfreie Sprachen, sorry. Übungsbuch A64 (PUM-AL) und A65 (PUM-AD) sind Fallunterscheidungen zu treffen. Muss ich diese Fallunterscheidung machen, oder kann ich wenn ich zu einem dieser Fälle einen Widerspruch aufzeige, die weiteren Fälle vernachlässigen?

Answer 1

Diese Fallunterscheidungen sind notwendig und essentiell! Wenn Sie einen Fall weglassen, ist das kein Beweis und Sie haben die Aufgabe nicht gelöst (Sie haben dann gerade eben nicht einen Widerspruch gezeigt!) - beachten Sie das auch für die Klausur!

Sie müssen ja für alle möglichen Zerlegungen des Testworts zeigen, dass wenn die Bedingungen (1) und (2) des PPLs gelten, dann Bedingung (3) nicht gelten kann. Sie wissen über diese Zerlegungen nur, dass sie die Struktur des Testworts haben und dass die Bedingungen (1) und (2) gelten. Wie sie exakt aussehen, wissen Sie nicht, also müssen Sie alle Möglichkeiten abdecken. Bei einfachen Aufgaben gibt es nur einen Fall, aber bei interessanteren Aufgaben können es auch zwei oder noch mehr sein.

Das PPL ist ein Beweisverfahren, und daher gibt es da wenig Raum für Schwammigkeiten (deshalb habe ich auch auf einer präzisen Formulierung der Frage bestanden). Sie können beim PPL also eher nicht mit viel Kulanz bei der Korrektur von falschen Lösungen rechnen.