0 Daumen
751 Aufrufe

Hallo liebe Community :)

Ich bin wirklich am verzweifeln und überlege schon lange wie ich diese Aufgabe lösen kann...

Deshalb bitte ich um eure Hilfe!

L={a2^n| n€{0,1,....}}
Wie kann ich beweisen, dass diese Sprache nicht regulär ist ?

Wahrscheinlich über Pumping Lemma, aber irgendwie weiß ich nicht wie ich das zerlegen müsste...

Danke im Voraus!!!

von

1 Antwort

+1 Daumen

Ist p die Pumping-Zahl und q ≤ p und

        a(p-q) aq ar ∈ L,

dann ist auch für eine bestimmten Wert von q

        a(p-q) (aq)m ar ∈ L

für jedes m∈ ℕ0. Für diesen Wert von q müsste laut Definition von L

        (p-q)+mq+r

für jedes m∈ ℕ0 eine Zweierpotenz sein.

Sei (p-q)+mq+r = 2k .

Das lässt sich umformen zu

        (p+r) + (m-1)q = 2k.

Dann ist

       2((p+r) + (m-1)q) = 2k+1.

Ausmultiplizieren und umformen

        (p+r) + (2m-1)·q + p + r - q = 2k+1.

Laut Definition von L ist (p+r) + (2m-1)·q ebenfalls  eine Zweierpotenz.

Wegen q ≤ p ist p+r-q≥0 und somit (p+r) + (2m-1)·q = 2k+1 und p+r-q = 0, also p+r=q.

Somit ist 2k = (p+r) + (m-1)q = q + (m-1)q = mq und 2mq = 2k+1 . Dann gilt

        2k = mq ≤ 2mq = 2k+1 ≤ (m+1)q 

genau dann wenn 2m ≤ m+1. Das gilt aber nur für m≤1.

wie ich das zerlegen müsste

Du zerlegst überhaupt nicht. Du zeigst, dass es keine Zerlegung laut Pumping-Lemma gibt.

von 5,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community