Pompowanie lematu dla regularnych gramatyk
Twierdzenie
Niech L będzie językiem zwykłym. Wtedy istnieje stała‘c’ takie, że dla każdego ciągu w w L -
|w| ≥ c
Możemy się złamać w na trzy struny, w = xyz, takie, że -
- | y | > 0
- | xy | ≤ c
- Dla wszystkich k ≥ 0, ciąg xy k z jest również w L.
Zastosowania lematu pompowania
Lemat o pompowaniu ma na celu pokazanie, że niektóre języki nie są regularne. Nie należy go nigdy używać, aby pokazać, że język jest normalny.
Jeśli L jest regularny, spełnia Lemat pompowania.
Jeśli L nie spełnia lematu pompowania, jest nieregularny.
Metoda udowodnienia, że język L nie jest regularny
Najpierw musimy to założyć L jest regularne.
Tak więc lemat o pompowaniu powinien się trzymać L.
Użyj lematu o pompowaniu, aby uzyskać sprzeczność -
Wybierz w takie że |w| ≥ c
Wybierz y takie że |y| ≥ 1
Wybierz x takie że |xy| ≤ c
Przypisz pozostały ciąg do z.
Wybierz k tak, że wynikowy ciąg nie znajduje się w L.
Hence L is not regular.
Problem
Udowodnij to L = {aibi | i ≥ 0} nie jest regularne.
Solution -
Na początku to zakładamy L jest regularne, a n to liczba stanów.
Niech w = a n b n . Zatem | w | = 2n ≥ n.
Pompując lemat, niech w = xyz, gdzie | xy | ≤ n.
Niech x = a p , y = a q , a z = a r b n , gdzie p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Zatem | y | ≠ 0.
Niech k = 2. Wtedy xy 2 z = a p a 2q a r b n .
Liczba as = (p + 2q + r) = (p + q + r) + q = n + q
Stąd xy 2 z = a n + q b n . Ponieważ q ≠ 0, xy 2 z nie ma postaci a n b n .
Zatem xy 2 z nie jest w L. Stąd L nie jest regularne.