1^n^2 beweis regulär?


0
und wieder hallo!!! ist die sprache 1^n^2 (n >= 0) regulär? wie beweißt man das?

 

gefragt vor 1 Jahr
j
janina,
Student, Punkte: 8
 
Kommentar schreiben Diese Frage melden
1 Antwort
2
Hallo Janina!

Auch hier arbeitest Du am besten mit dem Pumping-Lemma.

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\)

Melde Dich gerne, wenn Du Fragen zu den einzelnen Schritten hast. Und ganz wichtig: Übung macht die Meisterin!

Viele Grüße
André
geantwortet vor 1 Jahr
letsrockinformatik, verified
Student, Punkte: 4346
 

topp dankesehr!   -   janina, kommentiert vor 1 Jahr
Kommentar schreiben Diese Antwort melden