0 Daumen
190 Aufrufe

Wie beweist man, dass die Sprache L = {1^{n²} | n ≥ 0}  nicht regulär ist?

von

1 Antwort

+2 Daumen
 
Beste Antwort

Sei \(p\in\mathbb{N}\) die Pumping-Lemma-Zahl. Sei weiterhin \(w=1^{p^2}\in L\) und \(w=xyz\) mit \(|y|>0\) und \(|xy|\leq p\). Dann folgt für \(b\geq 1\) und \(a+b\leq p\) (also \(a\geq 0\)), dass \(x=1^a\), \(y=1^b\) und \(z=1^{p^2-a-b}\) ist. Wir wählen in \(w=xy^iz\) den Exponenten \(i=2\) und müssen zeigen, dass \(xy^2z=1^{p^2+b}\notin L\). Und dafür müssen wir zeigen, dass \(p^2+b\) keine Quadratzahl ist. Da \(b\geq 1\) ist \(p^2+b> p^2\) und mit \(a+b\leq p\) folgt, dass \(p^2+b\leq p^2+p< (p+1)^2\), wird \(p^2+b\) definitiv keine Quadratzahl sein können. Mit dem Pumping-Lemma für reguläre Sprachen folgt, dass \(L\) nicht regulär ist. \(\square\)

von 8,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...