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

Kategorien

1 Pluspunkt 0 Minuspunkte
262 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!
...