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 1 Minuspunkt
118 Aufrufe

EDIT: Der folgende Beitrag bezieht sich auf eine veraltete Version des Pools; er wird trotzdem nicht zensiert, damit die Diskussion in diesem Thread verständlich bleibt.

Hallo,

die Beweisstruktur in diesem Beweis ist nicht korrekt! Es wird etwas falsches gefolgert:

 

"...Jetzt sei w=xyz beliebige Partition von w. Dann gilt laut PPL:

1) |xy|≤n

2) |y|>0

3)...

"

Diese Folgerung ist doch falsch. Das PPL sagt nämlich, dass es eine Partition gibt, sodass 1-3 gilt. Also insbesondere, dass es nicht für eine beliebige Partition gilt! Sonst müsste es im PPL heißen, dass dies für jede(!) Zerlegung gilt.

lg Adam

 

in PUM-AA von uafjv uafjv Tutor(in) (168k Punkte)  
Bearbeitet von uafjv uafjv

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort
Hallo Adam, hallo Sven,

Adam hat trotzdem mit seiner Anmerkung recht - wir haben das nicht hundertprozentig korrekt formuliert. Wir werden das ändern zu:

"Es seien $x,y,z∈E^∗$ Wörter, sodass gilt: $w=xyz$ und [...] (1), (2), (3)"

(oder so ähnlich).

Viele Grüße

Lukas König
von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hallo,

danke erstmal für die Antwort, die neue Formulierung hört sich gut an.

Ich habe nicht gemeint, dass es nur eine einzige gibt, sondern mindestens eine, aber das war nicht eindeutig herauslesbar. Und dass es Wörter xyz gibt, sodass w=xyz ist wohl selbstverständlich, aber dass diese auch noch 1-3 des PPL erfüllen, stimmt eben nicht für alle. Wir wissen nur, dass min. eine Zerlegung dieser xyz das PPL erfüllt, deshalb müssen wir ja für alle Zerlegungen zeigen, dass sie 1-3 nicht erfüllen können, um den Widerspruchsbeweis zu führen.

Und in meinem Zitat wurde für alle w=xyz gefolgert, dass xyz 1-3 des PPL erfüllen. Wenn dies so wäre, müssten wir nur eine spezielle Zerlegung betrachten :D

lg Adam
Ist Widerspruchsbeweis durch definieren von xy & z zulässig?
0 Pluspunkte 0 Minuspunkte

Hallo,

das PPL besagt nicht explizit, dass es EINE Partion gibt, sondern es sagt, dass es Wörter x, y und z mit w = xyz gibt. Das schließt also nicht aus, dass man für x, y und z viele unterschiedliche Wahlen treffen kann und daraus w zusammen setzen kann.

Viele Grüße,

Sven (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...