alternative Argumentation: richtig?

Question

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.

 

Answer 1

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)

 

Comments

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

---

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)

---

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?

---

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)