b): Ist die Zerlegung in x,y,z beliebig ?

Question

Hallo, ich würde gerne wissen, ob meine Lösung bei der 4b) auch stimmt: also wort habe ich \( 0^{n}1^{n}0^{n} \) mit der Länge \( n^{3} \)gewählt.

\( x=0^{n-k} ; y=0^{k} ; z=1^{n}0^{n} \)

pumpvaiable i=2: \( 0^{n-k} 0^{2k} 1^{n} 0^{n} = 0^{n+k} 1^{n} 0^{n} \). Und das ist kein element der sprache und kann deshalb nicht vom EA akzeptiert werden. Stimmt das?

ich habe noch eine allgemeine frage zum pumping lemma: ist es völlig egal welche zerlegung ich als x,y und z wähle? Hautsache es kommt etwas raus was nicht zur sprache gehört?

Vielen dank im voraus

 

Answer 1

Hallo,

ja der von dir durchgeführte Beweis ist möglich. 

Zur allgemeinen Frage:

Beim PPL reicht es zu zeigen, dass es ein Wort \( w \in L\) mit \(  \mid w \mid \leq n \) gibt, sodass für alle Zerlegungen w=xyz mindestens eine der drei Forderungen nicht gilt. Grundsätzlich ist kann die Zerlegung frei gewählt werden.

Viele Grüße,

Sebastian (Tutor)