Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Fallunterscheidung Pumping Lemma zur Widerlegung der dritten Regel

+2 Punkte
149 Aufrufe
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.
Gefragt 17, Jan 2016 in Allgemeine Fragen von uagll uagll Lernwillige(r) (1,100 Punkte)  
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?

Eine Antwort

0 Punkte

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.

Beantwortet 17, Jan 2016 von Lukas König Dozent (10,065,100 Punkte)  
Bearbeitet 17, Jan 2016 von Lukas König
...