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

Kategorien

0 Pluspunkte 1 Minuspunkt
71 Aufrufe

Ich habe auch wie in der Lösung $w=0^n 1^n$ gesetzt. Kann ich dann wie folgt weiter beweisen?

$xy=0^n$ (somit ist der Betrag(xy)=n also PPL-Voraussetzung erfüllt)

$y=0^1=0$

$x=0^{n-1}$

$z=1^n$

mit (3) aus dem PPL folgt:

$w=xy^iz=0^{(n-1)^*} 0^{i^*} 1^n$

offensichtlich folgt mit i>1 das L nicht Teil eines EA ist.

 

in PUM-AA von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Nein, diese Argumentation ist leider nicht zulässig, da |xy| jede Anzahl kleiner gleich n (≤n) annehmen kann, du allerdings in deiner Argumentation die (exakte) Gleicheit voraussetzt.

Dadurch entstehen übrigens weitere Fehler bei dir, also bitte gleich Zeile 2 ändern und dann nochmal von vorne ;)

Gruß

Philip (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Danke für die Antwort, dann wäre das hier richtig:?

$w=0^n 1^n$

$xy = 0^j$ mit $j \leq n$ => $|xy| \leq n$

$x= 0^p$ mit $p<j$

$y= 0^{j-p}$

$z= 0^{n-j} 1^n$

mit dem PPL folgt:

$w'= 0^p 0^{i^*(j-p)} 0^{n-k} 1^n$

$ |0en |= p + i^*(j-p) + n-k$

somit kann man i die Anzahl der 0en hochgepumpt werden
0 0
Hallo,

jetzt stimmt es. Benutze in der Klausur trotzdem ein bestimmtes i. Für i=1 bekommt man ja noch kein Widerspruch.

Gruß,

Adam (Tutor)
0 0
Eine Frage hätte ich da aber noch. Ich habe xy ja wie folgt verteilt:

$xy = 0^j$ mit $j \leq n$ => $|xy| \leq n$
$x= 0^p$ mit $p<j$
$y= 0^{j-p}$

da $p<j$ gilt ist $|y|>1$, laut PPL muss jedoch $|y| \geq 1$ gelten. Ist das ein Fehler?
0 0
Nein, du kannst doch $p=j-1$ wählen, dann ist

$p=j-1 < j$ und $|y|= j-p = j-(j-1) = 1$.

Gruß,

Adam (Tutor)
...