Pumpinglemma für reguläre Sprachen

Einfache Sprache

Def. Pumpinglemma für reguläre Sprachen

Sei $A$ ein Alphabet und $L\subseteq A^*$ eine Sprache. Dann sind die beiden folgenden Aussagen äquivalent:

1. Die Sprache $L$ ist regulär.
2. Die Sprache $L$ besitzt die Pumpingeigenschaft.

Beweis: (1. -> 2.) Sei $L$ eine reguläre Sprache. Dann existiert nach Reguläre Sprache > Mit DEA ein DEA $\mathcal A = (\{0,1,\ldots, n-1\}, A,\delta,0,F)$ dessen Erkannte Sprache $L$ ist. Als Pumpingkonstante wählen wir $m = n$.

Nun müssen wir zeigen, dass $m$ wirklich eine Pumpingkonstante für $L$ ist, woraus folgen würde das $L$ die Pumpingeigenschaft hat. Dazu sein $w\in A^m$ ein beliebiges Wort. Sei $\sigma = q_0q_1\ldots q_n$ mit $q_0 = 0$ und $0\leq q_lBerechnung von $\mathcal A$ auf $w$. Aus $|\sigma| = n+1$ folgt nach dem Schubfachprinzip, dass ein Zustand in $\sigma$ mehrfach vorkommt. Also es existieren zwei Indizes $0\leq s

• $\hat\delta(q_0,x) = q_s$,
• $\hat\delta(q_s,y) = q_t = q_s$ und
• $\hat\delta(q_s,z) = q_n$. Den mittleren Teil $y$ erlaubt es uns beliebiges oft “im Kreis zu drehen”, also $\hat\delta(q_s,y^i) = q_s$ für alle $i\in\mathbb N$. Daraus folgt $\hat\delta(q_0,xy^iz) = q_n =\hat\delta(q_0,xy^jz)$ für alle $i,j\in\mathbb N$. Sei nun $v\in A^*$ ein beliebiges Wort. Dann ist $\hat\delta(q_0,xy^izv)=\hat\delta(q_0,xy^jzv), womit die Pumpingeigenschaft bewiesen ist.

Für (2. -> 1.) sei $L$ eine Sprache mit Pumpingeigenschaft. Dann hat $L$ eine Pumpingkonstante $m$. Es muss $m>0$ gelten, da es sonst keine Zerlegung von $\varepsilon$ gäbe ( #TODO warum?).

1. Hilfslemma: Zu jedem Wort $u\in A^m$ gibt es ein Wort $v\in A^*$ mit $|v| < m$ so, dass für alle $w\in A^*$ gilt: $uw\in L$ genau dann, wenn $vw\in L$. #TODO

2. Hilfslemma: Behauptung: Für jedes $u\in A^*$ und jedes $a\in A$ und alle $w\in A^*$ gilt $\hat\delta(q_I, u)w\in L$ genau dann wenn $uw\in L$. Beweis via Induktion über die Länge von $u$: IA: Sei $|u|< m$. Dann gilt nach #TODO

Wir konstruieren einen DEA $\mathcal A$ der $L$ erkennt wie folgt:

• Menge der Zustände: $Q = \{v \in A^* \mid |v| < m\}$,
• Transitionsfunktion:
  • $\delta'(u,a) = ua$ für $u \in A^*$ mit $|u| < m-1$ und $a \in A$.
  • $\delta'(u,a) = v_{u,a}$ für $u \in A^{m-1}$ und $a \in A$.
• Anfangszustand: $q_I = \varepsilon$ und
• Menge der Endzustände: $F = Q \cap L$.

Die Korrektheit von $\mathcal A$ ergibt sich aus folgender Gleichung für jedes Wort $u\in A^*$: