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.