Pompowanie lematu dla prostych skończonych języków regularnych

Wikipedia ma następującą definicję lematu pompującego dla zwykłych języków ...

Niech będzie zwykłym językiem. Następnie istnieje całkowita p ≥ 1 zależy wyłącznie od L , tak że każdy ciąg wagowych w L o długości co najmniej p ( p nazywany jest „pompowanie długość”) może być zapisane jako W = xyz (tj wag można podzielić na trzy podciągi), spełniający następujące warunki:p $L$$p$$L$L p p w x y z $w$$L$$p$$p$$w$$xyz$$w$

1. | $y$ | ≥ 1
2. | $xy$ | ≤ $p$
3. dla wszystkich $i$ ≥ 0, $xy^iz$ ∈ $L$

Nie rozumiem, jak to jest spełnione w przypadku prostego, skończonego języka regularnego. Jeśli mam alfabetu { $a,b$ } i wyrażenia regularnego $ab$ następnie $L$ składa się z tylko jednym słowem, które jest następnie b . Chcę teraz sprawdzić, czy mój zwykły język spełnia pompujący lemat ...$a$$b$

Ponieważ w moim wyrażeniu regularnym nic się nie powtarza, wartość $y$ musi być pusta, aby warunek 3 był spełniony dla wszystkich $i$ . Ale jeśli tak, to nie spełnia warunku 1, który mówi, że $y$ musi mieć co najmniej 1 długość!

Jeśli zamiast tego pozwolę $y$ być $a$ , $b$ lub $ab$ wówczas spełni warunek 1, ale nie spełni warunku 3, ponieważ tak naprawdę nigdy się nie powtarza.

Najwyraźniej brakuje mi czegoś oczywistego. Który jest?

Masz rację - nie możemy pozwolić na „pompowanie” słowa skończonego $L$ . Brakuje tego, że lemat mówi, że istnieje liczba $p$ , ale nie podaje nam liczby.

Wszystkie słowa dłuższe niż mogą być pompowane przez lemat. Dla skończonego , zdarza się tak, że jest większa niż długość najdłuższego słowa w . Zatem lemat zachowuje się jedynie próżniowo i nie można go zastosować do żadnego słowa w , tj. Każde słowo w nie spełnia warunku „długości co najmniej ”, jak wymaga tego lemat.L p L $p$$L$$p$$L$$L$$L$$p$

Następstwo: jeśli ma długość pompowania i istnieje jakieś słowo o długości co najmniej , to jest nieskończone.p w ∈ L p $L$$p$$w\in L$$p$$L$

Pompowanie lematu jest zwykle stosowane w nieskończonych językach, tj. W językach, które zawierają nieskończoną liczbę słów. Dla każdego skończonego języka , ponieważ zawsze może być zaakceptowany przez DFA ze skończoną liczbą stanów, musi być regularny.$L$$L$

Według wikipedii ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), pompowanie lematu mówi: $\begin{array}{l} (\forall L\subseteq \Sigma^*) \\ \quad (\mbox{regular}(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end{array}$

Dla dowolnego skończonego języka , niech będzie maksymalną długością słów w , i niech w pompowaniu lematu będzie . Lemat pompowania utrzymuje się, ponieważ w nie ma słów, których długość .l m a x L p l m a x + 1 L ≥ l m a x + $L$$l_{max}$$L$$p$$l_{max}+1$$L$$\geq l_{max}+1$

Jednym ze sposobów sformalizowania podstawowej części lematu Pompowanie jest użycie :$L^{\geq k} = \{ w \in L \mid |w| \geq k\}$

Jeśli jest regularne, istnieje więc$L$$p \in \mathbb{N}$

$\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (*).

Dla wszystkich skończonych i , oczywiście mamy . Dlatego (*) jest (próżno) prawdziwe dla takiego .p > max { | w | ∣ w ∈ L } L ≥ p = ∅ $L$$p > \max \{ |w| \mid w \in L\}$$L^{\geq p} = \emptyset$$p$