Przedstawię Ci tutaj treść i dowód lematu o pompowaniu dla języków regularnych. Zakładam, że znasz podstawowe definicje takie jak DFA czy rozszerzona funkcja przejścia dla DFA.
Twierdzenie
Niech \(L = L(\mathcal{A})\), gdzie \(\mathcal{A}\) jest deterministycznym automatem skończenie stanowym. Istnieje wówczas taka liczba naturalna \(n > 0\), że dowolne słow \(P \in L\), \(|P| \geq n\) (jest niekrótsze od ) można przedstawić w postaci konkatenacji takich słów \(P = XYZ\) (\(X, Y, Z \in L\)), że:
- \(Y \neq \epsilon\),
- \(|XY| \leq n\),
- \(\forall k \in \mathbb{N}\) słowo \(XY^kZ \in L\).
Dowód
Niech \(L = L(\mathcal{A})\) jest akceptowany przez deterministyczny automat skończenie stanowy): \(\mathcal{A} \ (K, T, \delta, q_0, F)\) i \(n = \overset{=}{K}\) (moc zbioru stanów automatu).
\(P = a_1a_2 \dots a_m\), niech \( m\geq n\).
Słowo \(P \in L\), więc \(\hat{\delta}(q_0,a_1 a_2 \dots a_n) = q_h, q_h \in F\).
Stanów w redukcji \(q_0P\) jest \(m+1\), różnych stanów w \(\mathcal{A}\) jest \(n\). W taqkim razie w trakcie redukowania słowa \(P\) przez \(\mathcal{A}\), co najmniej jeden stan musi się powtórzyć.
Wybieramy taki stan z redukcji słowa \(P\), który powtórzy się jako pierwszy w całej redukcji, oznaczamy go jako stan \(q\).
Dostajemy w ten sposób podział słowa \(P\) na prefiks, podsłowo i sufiks wyznaczone przez wystąpienia stanu \(q\).
\[ X = a_1 \dots a_k \quad Y = a_{k+1} \dots a_l \quad Z = a_{l+1} \dots a_m \]
\[ \hat{\delta} (q_0, X) = q \quad \hat{\delta}(q, Y) = q \quad \hat{\delta}(q, Z) = q_h \]
Teraz musimy pokazać, że 3 warunki dla słowa \(XYZ\) zachodzą:
- \(Y \neq \epsilon\)
- \(|XY| \leq n\), nierówność ta zachodzi ponieważ w redukcji słowa \(XY\) żaden stan się nie powtarza (wszystkie są różne więc na pewno jest ich nie więcej niż \(n\), które jest liczbą stanów z \(\mathcal{A}\)),
- Najpierw przez indukcję pokazujemy, że: \(\forall n \geq 0 \quad \hat{\delta} (q_0, XY^n) = q\)
Sprawdzamy czy równość zachodzi dla \(n=0\):
\[ \hat{\delta} (q_0, XY^n) = \hat{\delta}(q_0, XY^0) = \hat{\delta}(q_0, X \epsilon) = \hat{\delta} (q_0, X) = q \]
Zakładamy, że:
\[ \hat{\delta}(q_0, XY^n) = q \]
Teza:
\[ \hat{\delta} (q_0, XY^{n+1}) = q \]
\[ \hat{\delta} (q_0, XY^{n+1}) = \hat{\delta} (q_0, XY^nY) = \hat{\delta}(\hat{\delta}(q_0, XY^n), Y) \overset{\textrm{zał}}{=} \hat{\delta}(q,Y) = q \]
Teraz już tylko musimy pokazać, że \(XY^k Z \in L\) czyli następującą równość:
\[ \hat{\delta} (q_0, XY^k Z) = q_h \]
Sprawdzamy czy równość zachodzi dla \(k=0\):
\[ \hat{\delta} (q_0, XY^kZ) = \hat{\delta} (q_0, XY^0 Z) = \hat{\delta} (q_0, XZ) = \]
\[ \hat{\delta} ( \hat{\delta}( q_0, X ), Z) = \hat{\delta} (q,Z) = q_h \]
Zakładamy, że:
\[ \hat{\delta} (q_0, XY^k Z) = q_h \]
Teza:
\[ \hat{\delta} (q_0, XY^{k+1}Z) = q_h \]
\[ \hat{\delta} (q_0, XY^{k+1} Z) = \hat{\delta} (\hat{\delta} (q_0, XY^{k+1}), Z) \overset{\textrm{Lemat}}{=} \hat{\delta}(q,Z)= q_h \]