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
74 Aufrufe
Ist folgende Lösung auch zulässig?

Sei z = 0^k 1^k 0^k 1^k

(1) |vwx| <= k --> kann maximal zwei der vier Gruppen (0/1/0/1) enthalten.

Sei s, t e N0, i=0 die Pumpvariable & damit das gepumpte Wort

       z'= u v^0 w x^0 y = uwy

1. Fall: vx enthält keine der zwei hinteren 0en oder 1en

|vx| = 0^s 1^t

--> z' = 0^k-s 1^k-t 0^k 1^k

2. Fall: vx enthält keine der vorderen 1en oder hinteren 0en

....(siehe oben)

3. Fall: von enthält keine der vorderen 0en oder 1en

....

Da s +t >= 1 (2. Bedingung ) stimmt bei jedem der Fälle die Anzahl der 1. Nullen mit den 2. Nullen  bzw die Anzahl der 1. Einsen mit den 2. Einsen nicht überein.
in PUM-AJ von  

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Hallo,

wenn ich Ihre Idee richtig verstehe, kann das so nicht klappen. Durch $i=0$ fallen ja $s$ Nullen und $t$ Einsen weg. Wenn aber $s=t$ ist, dann bleibt die Anzahl an Einsen gleich der Anzahl der Nullen im Wort.

Viele Grüße

Lukas König
von Dozent (10.1m Punkte)  
...