Yazan : Şadi Evren ŞEKER

Bir dilin Düzenli ifadele (Regular expression) olup olmadığının belirlenmesi için kullanılan pomplama önsavıdı (pumping lemma). Basitçe düzenli ifadede olup olmadığı sınanacak bir w dili için (yani L = w için)

w= xyz

şeklinde bir açılım sınanır. Buradaki sınama sırasında aşağıdaki koşulların sağlanması beklenir:

  1. |y| ≥ 1
  2. |xy| ≤ p
  3. bütün i ≥ 0 için, xyizL

Yukarıdaki üç şartı da sağlayan bir dil için düzenli ifadedir denilebilir. Ayrıca bu dilin düzenli ifade olabilmesi için yukarıdaki y teriminin üstü olan i değeri istenildiği kadar arttırılabilmeli ve elde edilen sonuç yine düzenli ifade (Regular expression) olmalıdır.

Daha basit bir ifadeyle, bir dilden üretilen bir terim üç parçaya bölündüğünde ortasındaki parça boş olmamalı, istenildiği kadar tekrarlanabilmeli ve çıkan bütün sonuçlar yine aynı dilden olmalıdır.

Örnek:

Pompalama önsavı konusunda en çok verilen örneklerden birisi L = {anbn : n ≥ 0} dilinin bir düzenli ifade olmadığının ispatıdır. Bu örneği beraberce ispatlayalım:

Dilimizi pompalama önsavındaki kalıp olan w = xyz şekline benzetmeye çalışalım. Bu durumda dilimizdeki üretilebilen en kısa terim için w = apbp olduğu söylenebilir ve bu terimi kalıba benzetirken xy için a ve z için b olduğunu söyleyebiliriz. Çünkü y’nin sıfır boyutunda olamayacağını biliyoruz, bu durumda y değeri ya a ya da b olmalıdır. İki durumda birbirinin aynısıdır. Bu durumda

y=a

z=b

olarak kabul edelim.

Şimdi sonucumuzu pompalayalım ve bir sonraki beklentimiz olan xy2z terimini üretelim. Bu durumda çıktımız w = a2b olacaktır. Dikkat edilirse bu yeni terim, dil tanımımız olan L = {anbn : n ≥ 0} tanımı ile çelişmektedir ve bu dilin bir üyesi değildir.

Dolayısıyla L = {anbn : n ≥ 0} dilinin bir düzenli ifade olmadığı veya düzenli ifade olarak yazılamayacağı ispatlanmış olur.

Örnek Çözüm :

Mesut Aydın bey efendinin sorusuna istinaden aşağıdaki çözümü yazıyorum:

Sorunun tam metnini kendileri yorum olarak bu sayfada yazmışlar ancak bir kerede buraya alıntılıyorum:

L dili için (x ∈ (0,1)* ve W=XX^R) Pumping lemma ile regülerliğini araştırın.
Örneğin : x = 011 olsun x^R =110 olur ve w=011110 olur.

Zannediyorum x^R ile ifade edilmek istenen, x teriminin tersi oluyor.

Şimdi bakın böyle bir soruda doğrudan cevap olarak RE (Regular Expression) olamayacağını söyleyebilirim (biraz tecrübe ile biraz da olaya şu şekilde bakmanız gerekiyor) Bunun sebebi, basitçe herhangi bir RE için sadece bir pompalama noktasına izin verilmesidir. Diyelim ki x için değişim belirttiniz, bu durumda x^R ‘nin buna bağlı değişmesi soruda bir şart olarak tanımlanmış, oysaki biz sadece tek noktada pompalama yapabiliyoruz ve dolayısıyla x değişirken x^R şeklinde verilen ikinci kısma müdahale edemiyoruz.

Daha akademik olarak durumu ifade edecek olursak:
Yukarıda verilen W non-regular (düzenli olmayan bir ifadedir).

İspatı : L dilini (L tanımıyla üretilebilecek kelimeler kümesini) öncelikle düzenli ifade kabul edelim (regular expression)
Bu kabul doğruysa, n>1 uzunluğunda bir pompalama uzunluğu bulunmalıdır ki W∈L olsun ve her |w| ≥ n  için x = klm yazılabilsin. (Burada klm üç harfini kullandım bunun sebebi aslında yukarıda anlatılan ve yazıda geçen xyz kullanırsak x harfinin sorudaki x ile karışması endişesidir. Soruda x harfi kullanıldığı için (L’den üretilebilen herhangi bir kelime olarak) bu harfi tekrar kullanmadım). Ayrıca bu klm üç harfi için aşağıdaki şartlar da sağlanmalıdır:

  • |kl|≤n
  • |l|>0
  • son olarak klim ∈ L bütün i ≥ 0 değerleri için sağlanmalıdır.

Şimdi yukarıda yazdığımız ve pompalama önsavının tanımındana gelen durumları çürüten bir örnek bulursak, bu L dilinin düzenli ifade olmadığını, olmayana ergi (burhan-ı mütanakis, proof by contradiction) yöntemi ile ispat etmiş olacağız:

Örneğin X = 0n olarak verilmiş olsun. Bu durumda W = 0n 0n olacaktır çünkü 0n teriminin tersi yine kendisidir.

Yukarıdaki örnek W için W  ∈ L rahatlıkla denilebilir. Çünkü soruda verilen tanımı sağlamaktadır. Ayrıca dikkat ediniz W terimi X ve X^R terimlerinden mürekkep olduğu için bu terimin boyu her zaman çifttir yani |W| her zaman çift bir sayıdır diyeibliriz. Çünkü X ile X^R kelimelerinin boyu eşittir. Yani bir kelimenin boyu ile tersinin boyu eşit olduğu için bu iki kelimeden oluşan W’nun boyutu tabii olarak çift sayı olacaktır.

Pompalama önsavından öğrendiğimiz üzere, W terimi n adet 0 ile başladığına göre, herhangi bir j sayısı, 0 ≤ j ≤ n şartını sağlamak üzere, pompalama önsavından gelen tanım itibariyle l = oj olur denilebilir. Yani diğer bir deyişle, klm dizilimindeki l teriminin pompalanacağını biliyoruz ve bu terim soruda verilen W ifadesini gösterebilmek için oj olarak seçilmeli ki pompalama neticesinde 0n terimine ulaşılsın (veya 0n terimine ulaşılana kadar pompalansın).

Örneğin klim ifadesi için i = 0 kabul edilirse kl0m = km = 0n-j 0n

olacaktır. Ayrıca bu terimin de bir W terimi olduğunu ve W’nun tanımında bulunan şartları sağladığını söyleyebilmeliyiz.

Ancak, n> n-j (j>0 olduğu için) olduğuna göre ve ayrıca j teriminin tek veya çift olması ile ilgili herhangi bir bilgi olmadığına göre. j teriminin tek olması halinde km teriminin eleman sayısının tek sayı olduğu görülür. Bu durumda tanım itibariyle çift sayıda eleman içermesi gereken W teriminin tek sayıda terim içerebileceği de görülmüş olur. (Bu durumda bir çelişki oluşuyor ve ispatını üzerine kurduğumuz üzere L dilinin RE olması kabulu çökmüş oluyor (contradiction)

Demek ki soruda verilen W terimi pompalama önsavına göre tek sayıda terim içerebilmektedir. Oysaki tanım itibariyle W bu şekilde bir terim asla olamaz.

Soruya bu şekilde cevap verdikten sonra, daha iyi anlaşılması açısından durumu şu şekilde izah edeyim:

Düzenli ifadelerde kullanabileceğimiz ve tekrar ifade eden tek işlemimiz (operator) ne yazık ki kleene yıldızı (kleene star) ismi verilen ve * sembolü ile gösterilen semboldür. Bu sembolün kaç kere tekrar edeceğini bilemeyiz.

Yukarıdaki soruda X için * kullanılması halinde X^R için yıldız kullanılamaz. İkisi için de kullanılırsa farklı miktarlarda tekrarlar olabilir. Bunun için iki veya daha fazla sayıdaki tekrar eden terimin birbirine eşit olması istenen durumlarda (ki bu örnek ve daha önce yazıda verdiğim örnekte de aynı durum söz konusu) RE olarak yazılamayacağını söyleyebiliriz çünkü kleen star kontrolsüz bir operatördür.

Buna karşılık tekrarlı terim sayısı 2 ise ve eşitlik isteniyorsa CFG olarak yazılabilir. Bunun için de CFG konusunda geçen pompalama önsavına (pumping lemma) bakabilirsiniz.

Yorumlar

  1. Mesut AYDIN

    İyi günler hocam.
    Gecen girdiğimiz sınavda Pumping lemma ile ilgili soru çıktı.
    Burda anlatılanlarla yapmaya çalıştım ama beceremedim.
    Birde size danışayım dedim.
    L dili için (x €(0,1)* ve W=XX^R) Pumping lemma ile regülerliğini araştırın.
    Örneğin : x = 011 olsun x^R =110 olur ve w=011110 olur.

  2. Murat İnan

    merhaba hocam,
    1. örnekte y için a ya da b olabilir ikisi de aynı demişsiniz. fakat |xy|≤p olduğundan y=b için kurala dilin kuralına uymuyor.

  3. kazım

    hocam merhaba size bi sorum olacak hemen çözmeniz mümkün olursa çok sevinirim soru şu:Alfabesi {0, 1} olan ve sağdan dördüncü sembolü sıfır olan kelimeleri içeren dilin
    düzenli bir dil olup olmadığını Pumping Lemma ile ispatlayınız.

kazım için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir