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

0 Pluspunkte 1 Minuspunkt
147 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)  
...