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 0 Minuspunkte
105 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)  
...