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!
 

 

Reicht ein speziefisches Wort zur Widerlegung des Pumpinglemmas?

+1 Punkt
152 Aufrufe
Hallo,

reicht es nicht nur ein ganz speziefisches Wort einer Sprache zu suchen und dort genau x,y und z zu benennen ohne irgendwelche Hochzahlen?

Es handelt sich beim Pumpimglemma ja um einen Widerspruchsbeweis bei dem es eigentlich ja genügen sollte nur eine Möglichkeit zu finden es zu widerlegen. Wenn es ein Wort gibt für das das Pumpinglemma nicht gilt dann kann es ja auch nichtmehr für alle Wörter gelten.
Gefragt 26, Jan 2017 in PUM-AA von Anonym  
Kurze Antwort: nein! Schauen Sie sich das PPL unbedingt nochmal an!

Eine Antwort

+1 Punkt
Hallo,
da hast du die Grundlegende Idee hinter dem PPL noch nicht so ganz verstanden. Wir versuchen ja beim PPL gerade durch die Verwendung der Hochzahlen zu zeigen, dass wir für ALLE n und für ALLE Zerlegungen des Wortes mindestens EINE mögliche Pumpvariable finden, bei der es zu einem Widerspruch kommt.
Also kannst du eben nicht nur ein mögliches Wort finden, sonder musst es für alle n zeigen. Jede EA-Sprache muss ja auch nur für EIN n EINE Zerlegung besitzen, für die wirklich alle Pumpmöglichkeiten noch Teil der Sprache sind. Schau dir am besten nochmal die Folie 29 im 2. Kapitel an da steht das ganz gut erklärt.
Ich hoffe das hat dir ein bisschen geholfen.
Beantwortet 26, Jan 2017 von updrq updrq Tutor(in) (103,620 Punkte)  
Schauen Sie sich mal das entsprechende Kapitel im Lehrbuch an (ab Seite 207). Wir haben diesen Teil besonders ausführlich beschrieben, weil Studierende immer wieder Probleme mit dieser "umgekehrten" Argumentation beim PPL haben.

Das ist natürlich auch für die Klausur ein wichtiges Thema!
...