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 0 Minuspunkte
114 Aufrufe
Hallo, ich wollte Fragen, ob auch eine alternative Zerlegung hier möglich wäre:

1. Fall vx enthält mindestens eine 0

dann enthält vx keine 2 oder 3. Entsprechend wäre bei eine i>1 die Anzahl der 0 größer als die der 2 und 3 und somit das Pumpwort nicht Teil der Sprache

2. Fall vx enthält keine 0

(1) vx enthält mind. eine 1 (2) vx enthält mind eine 2 (3) vx enthält mind eine 3

(1) für i=0 gibt es dann im Pumpwort mehr 0 als 1 entsprechend nicht Teil der Sprache

(2) für i=0 gibt es dann im Pumpwort mehr 0 als 2 entsprechend nicht Teil der Sprache

(3) für i=0 gibt es dann im Pumpwort mehr 0 als 3 entsprechend nicht Teil der Sprache

=> damit kann man einen Widerspruch feststellen

 

Wären in diesem Fall alle Zerlegungen berücksichtigt? Ich bin mir da nicht ganz sicher. Vielen Dank im Voraus
in PUM-AG von  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

deine Unterscheidungen im zweiten Fall überschneiden sich: wenn $vx$ eine $1$ oder eine $3$ enthält, kann es trotzdem auch eine $2$ enthalten.

Außerdem folgt im zweiten Fall für (1) nicht direkt, dass das gepumpte Wort nicht in der Sprache liegt: Mehr $0$en als $1$en sind grundsätzlich erlaubt, solange $\vert z\vert _0=\vert z \vert _2$ und $\vert z\vert _1=\vert z \vert _3$ gilt. Das gleiche gilt auch für die anderen Fälle.

Viele Grüße

Julia (Tutorin)
von uodvo uodvo Tutor(in) (107k Punkte)  
...