4. pumping lemma

pumping lemma

  • M

    Hallo leute!

    ich versuche gerade zu zeigen, dass die sprache L nicht regulär ist:
    L={02n∣n>0}L = \{ 0^{2^n} | n > 0\}

    bin mir nicht sicher ob der beweis so richtig ist:

    Sei L regulaer, n die ganze zahl aus dem pumping-lemma
    und w=02nw = 0^{2^n}
    ⇒w\Rightarrow w kann geschrieben werden als
    w=xyizw = xy^{i}z, wobei ∣xy∣≤n|xy| \le n und ∣y∣≥1|y| \ge 1.
    sei:
    x=0sx = 0^s
    y=0ky = 0^k
    z=02n−s−kz = 0^{2^n - s - k}
    mit 1≤k≤n−s1 \le k \le n - s

    sei nun i=2i = 2
    ⇒w=0s02k02n−s−k=02n+k\Rightarrow w = 0^s0^{2k}0^{2^n - s - k} = 0^{2^n + k}

    es gilt: ∣02n+k∣≤∣02n+n∣<∣02n+1∣|0^{2^n + k}| \le |0^{2^n + n}| < |0^{2^{n+1}}|
    (ich habe mit induktion gezeigt, dass 2n+n<2n+12^n + n < 2^{n+1} für alle n≥1n \ge 1 gilt)
    ⇒∣02n+k∣\Rightarrow |0^{2^n + k}| ist keine zweierpotenz
    ⇒\Rightarrowannahme war falsch
    ⇒w∉L\Rightarrow w \notin L
    ⇒\Rightarrow L nicht regulär

    danke!

    Gruß mathik

    0
  • 0

    wie kommstn du von
    i=2i = 2

    auf
    w=0s02k02n−s−kw = 0^s0^{2k}0^{2^n - s - k}

    müsste das nich
    w=0s0202n−s−2w = 0^s0^20^{2^{n - s - 2}}

    sein?

    0
  • M

    0rp schrieb:

    wie kommstn du von
    i=2i = 2

    auf
    w=0s02k02n−s−kw = 0^s0^{2k}0^{2^n - s - k}

    müsste das nich
    w=0s0202n−s−2w = 0^s0^20^{2^{n - s - 2}}

    sein?

    ich denke nicht, denn:
    y=0ky = 0^k
    y eingesetzt in w mit i = 2:
    w=0s(0k)202n−s−k=0s02k02n−s−kw = 0^s(0^{k})^{2}0^{2^n - s - k} = 0^s0^{2k}0^{2^n - s - k}

    sind doch potenzregeln 😉

    Gruß mathik

    0
  • J

    Hallo,

    Hab jetzt nur kurz drüber geschaut, sieht aber korrekt aus.

    MfG Jester

    0
Anmelden zum Antworten