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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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