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

0 Pluspunkte 0 Minuspunkte
94 Aufrufe

wenn wir in z jetzt bei kontextfreien Sprachen z.b. kein Mal durch die Schleife laufen, was ja genau dem i = 0 entsprechen müsste, dann habe ich doch nicht mehr mit Sicherheit gegeben, dass |z| >= n ist. Damit wäre dann doch auch die Grundlage der Eigenschaften für die Argumentation des PPLs hinfällig, oder nicht?

Wie wäre das dann analog bei dem PPL der regulären Sprachen zu verstehen?

 

Die Frage bezieht sich auf diesen Beitrag: https://info2.aifb.kit.edu/qa/index.php?qa=5207&qa_1=pumpen-mit-i-0

bezieht sich auf eine Antwort auf: Pumpen mit i=0
in PUM-AF von uzmzu uzmzu Lernwillige(r) (260 Punkte)  
Bearbeitet von uzmzu uzmzu

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
Beste Antwort
Hallo,

das muss auch nicht gelten für i=0, wie du ja schon geschrieben hast, die Schleifen müssen nicht durchlaufen werden.

Die Sprache muss Pumpstellen haben (sonst könnte man nur endlich viele Wörter erzeugen).

Die Idee dahinter ist eine andere: Du nimmst ein Wort z, das mindestens n Zeichen lang ist. Dies ist die Vorraussetzung.
Dein gewähltes Wort z beinhaltet also auch eine Pumpstelle, sonst wäre es nicht mindestens n Zeichen lang. Die Schleife muss aber nicht zwangsläufig durchlaufen werden (i=0), dann ist das modifizierte Wort möglicherweiße kürzer als n Zeichen, aber es muss immer noch zur Sprache gehören, da man die Pumpstelle (von z) beliebig oft pumpen kann (i=0,1,2,...).
Also ist die Grundlage nicht hinfällig, da immer noch gilt |z| >= n.

Das selbe Prinzip gilt auch bei dem PPL für reguläre Sprachen.

Ich hoffe es ist nun klarer, wenn du noch Fragen hast kannst du gerne noch einmal schreiben.

Viele Grüße
Anne (Tutor)
von uvlwv uvlwv Eins-Komma-Null-Anwärter(in) (3.3k Punkte)  
ausgewählt von uzmzu uzmzu
...