Was passiert bei $m=0$?

Question

Hallo,

was würde denn passieren, wenn ich für $m=0$ wähle? Nach Definition ist das ja zulässig. In diesem Fall würde ich  ein Wort haben, welches nur aus $a^n$ besteht, und ich könnte beliebig pumpen. Damit hab ich aber meinen Beweis ja entkräftet, weil ich ein Gegenbsp gefunden habe.

 

Answer 1

Solch ein Bespiel wie das von dir angeführte $w=a^n$ entkräftet deinen Beweis nicht. Das Pumpinglemma sagt aus, dass man ALLE Wörter w einer regulären Sprache mit $|w| \geq n$ gemäß der Angaben im Lemma so zerlegbar sind, dass man entsprechend pumpen kann.

Das Pumpinglemma schließt nicht aus, dass nicht-reguläre Sprachen oder eine Teilmenge einer nicht-regulären Sprache trotzdem das Pumpinglemma für reguläre Sprachen erfüllen können (siehe dazu auch Heimübung 3, Aufgabe 4).

Der Beweis, dass eine Sprache nicht regulär ist, ist ein Widerspruchsbeweis. Bei einem Widerspruchsbeweis reicht ein einziges Beispiel, das zu einem Widerspruch zur Annahme führt, aus, um die Annahme zu widerlegen.

Tobias (Tutor)