Normal Gramerler İçin Lemma Pompalama
Teoremi
L normal bir dil olsun. Sonra bir sabit var‘c’ öyle ki her dizge için w içinde L -
|w| ≥ c
Kırabiliriz w üç dizeye, w = xyz, öyle ki -
- | y | > 0
- | xy | ≤ c
- Tüm k ≥ 0 için, xy k z dizisi de L'dir.
Lemma Pompalama Uygulamaları
Pompalama Lemma, belirli dillerin düzenli olmadığını göstermek için uygulanacak. Asla bir dilin düzenli olduğunu göstermek için kullanılmamalıdır.
Eğer L düzenli, Pompalama Lemması'nı tatmin ediyor.
Eğer L Pumping Lemma'yı tatmin etmiyor, düzenli değil.
L dilinin düzenli olmadığını kanıtlama yöntemi
İlk başta şunu varsaymalıyız L düzenli.
Yani, pompalama lemması tutmalı L.
Bir çelişki elde etmek için pompalama lemmasını kullanın -
Seçiniz w öyle ki |w| ≥ c
Seçiniz y öyle ki |y| ≥ 1
Seçiniz x öyle ki |xy| ≤ c
Kalan dizeyi atayın z.
Seçiniz k sonuçta ortaya çıkan dize L.
Hence L is not regular.
Problem
Kanıtla L = {aibi | i ≥ 0} normal değil.
Solution -
İlk başta bunu varsayıyoruz L düzenli ve n durum sayısıdır.
W = a n b n olsun . Böylece | w | = 2n ≥ n.
Lemma pompalayarak w = xyz, burada | xy | ≤ n.
X = a p , y = a q ve z = a r b n olsun , burada p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Böylece | y | ≠ 0.
K = 2 olsun. O zaman xy 2 z = a p a 2q a r b n .
As sayısı = (p + 2q + r) = (p + q + r) + q = n + q
Dolayısıyla, xy 2 z = a n + q b n . Q ≠ 0 olduğundan, xy 2 z, a n b n biçiminde değildir .
Dolayısıyla, xy 2 z L'de değildir. Dolayısıyla L düzenli değildir.