Beweis zu einer Aufgabe schreiben. Wie kann ich beweisen, dass diese Sprache nicht regulär ist ?

Question

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={a^{2^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!!!

Answer 1

Ist p die Pumping-Zahl und q ≤ p und

        a^(p-q) a^q a^r ∈ L,

dann ist auch für eine bestimmten Wert von q

        a^(p-q) (a^q)^m a^r ∈ L

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

        (p-q)+mq+r

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

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

Das lässt sich umformen zu

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

Dann ist

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

Ausmultiplizieren und umformen

        (p+r) + (2m-1)·q + p + r - q = 2^k+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 = 2^k+1 und p+r-q = 0, also p+r=q.

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

        2^k = mq ≤ 2mq = 2^k+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.