Zeige, dass die Sprache L = {w ∈ {a,b}∗ | |w|a |w|b} (Anzahl der a’s ist größer als Anzahl der b’s) nicht regulär ist.

Question

Frage:

Zeige, dass die Sprache L = {w ∈ {a,b}∗ | |w|a > |w|b} (Anzahl der a’s ist größer als Anzahl der b’s) nicht regulär ist.

Code:

Also ich habe mit dem pumping lemma gearbeitet.

Sei n∈ℕ beliebig.

Wähle z=a^2^n b^n. Dann ist |z|=3n>n

Sei z= uvw eine beliebige Zerlegung mit |uv|≤n und |v|≥1.

Daraus folgt v=a^|v| u= a^l^-|v| w=a^2^n^-l b^n

Wähle i=2 dann ist uv^2w=uvvw=a^l^-^|v| a^2|v| a^2^n^-l b^n= a^2^n^+^|v| b^n nicht regulär.

Answer 1

Wenn du i=2 wählst pumpst du auf. Damit erhöhst du die Anzahl an a's egal welcher Zerlegung. Also ist dein Zielwort immernoch in der Sprache. Hiermit kannst du (auch mit dem PL) nicht zeigen, dass deine Sprache nicht regulär ist. Dafür müsste dein Zielwort nicht mehr in deiner Sprache liegen.

Du musst daher also hierbei abpumpen. Wähle also i=0.

Dann siehst du, dass bei einigen Zerlegungen deines Wortes dies noch schief geht. Daher solltest du ein Wort wählen, welches "gerade so" in der Sprache liegt, nämlich a^n b^{n-1}. Dabei ist die Anzahl an a's gerade so (echt) größer der Anzahl b's und wenn du dann ein v, welches in deinem a-Block liegst abpumpst, so ist die Anzahl der a's nicht mehr (echt) größer der Anzahl an b's. Damit folgt dann mit dem Pumping Lemma, dass die Sprache nicht regulär ist.

Comments

Ok danke, hätte ich es quasi auch anders herum machen können? Also b^2n a^n? Dann wäre es ja auch nicht regulär.

---

nicht mit 2n und n aber mit b^{n}a^{n+1} und dann entsprechend auf- statt abpumpen, also i >= 2.
b^{2n}a^n ist nicht in deiner sprache, da n<2n und eignet sich daher nicht.