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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
212 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.
in PUM-AA von  
0 0
Kurze Antwort: nein! Schauen Sie sich das PPL unbedingt nochmal an!

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
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.
von updrq updrq Tutor(in) (104k Punkte)  
1 0
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!
...