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.)

alternative Argumentation: richtig?

–1 Punkt
53 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.

 

Gefragt 25, Nov 2014 in PUM-AA von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 25, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
...