Negation der Pumpingeigenschaft

Einfache Sprache

Def. Negation der Pumpingeigenschaft

Eine Sprache hat die Negation der Pumpingeigenschaft wenn es für jede Zahl $m$ ein Wort $w\in A^m$ mit der folgenden Eigenschaft gibt: Für jede Zerlegung von $w$ der Form $w=xyz$ mit $x,z\in A^*$ und $y\in A^+$ gibt es ein Wort $v\in A^*$ und eine Zahl $i$ so, dass entweder:

• $wv\not\in L\land xy^izv\in L$ oder
• $wv\in L\land xy^izv\not\in L$.

Satz a^nb^n ist nicht regulär

eine nicht reguläre Sprache

Behauptung: $L=\{a^nb^n\mid n\in\mathbb N\}$ ist nicht regulär. Beweisidee: Wir zeigen die Negation der Pumpingeigenschaft für $L$ und folgen daraus das $L$ nicht regulär ist. Beweis: Sei $m\in\mathbb N$. Wir setzen $w_m = a^m$ und nehmen an das $w_m$ in $w_m = xyz$ mit $|y|>0$ zerlegt werden kann. Wir setzen $v_{x,y,z} = b^{|xyz|} = b^m$ und $i_{x,y,z}= 0$. Dann gilt $w_mv_{x,y,z} = a^mb^m\in L$ und wegen $|y|>0$ und daher $m - |y| < m$ gilt $xy^{i_{x,y,z}}zv_{x,y,z} = a^{m-|y|}v \not\in L$. Die Sprache besitzt also die negierte Pumpingeigenschaft und ist deshalb nicht regulär.