Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde bir dilin, içerik bağımsız gramer (context free grammer, CFG) ile gösterilemeyeceğini ispatlamaya yarar. Yani pompalama ön savı sayesinde bir dilin CFG olmadığı ispatlanabilir ancak olduğu ispatlanamaz. Şayet pompalama önsavını geçemyorsa CFG değildir denilebilir ancak geçmesi olmasını gerektirmez.
Pomplama önsavı (pumping lemma) kısaca bir dili aşağıdaki gramere uydurmaya çalışır:
- s = uvxyz
Elimizde ispatı ile uğraştığımız L dili olsun ve yukarıdaki s kelimesini bu dilden bir kelime olarak üretelim. Ve bu kelime |vxy| ≤ p, |vy| ≥ 1 (p burada pompalama boyutudur) şartlarını sağlasın. Şimdi bu kelimeyi aşağıdaki şekilde pompayalım:
s = uv ixy iz
Şayet bu pompalama sırasında üretilen i ≥ 0 için kelimelerde L dilindense o halde bu dil içerik bağımsız gramer CFG ile ifade edilebilir, şayet oluşan kelimeler L dili tarafından kapsanmıyorsa bu durumda da L dili, CFG olarak ifade edilemez sonucuna varılabilir.
Örnek:
Pompalama önsavını (pumping lemma) kullanarak aşağıdaki dilin CFG olmadığını ispatlayalım:
L = {aibici | i > 0}
Yukarıdaki dili, tanımımızdaki
- s = uvxyz
şekline getirmeye çalışalım ve bu sırada |vxy| ≤ p, |vy| ≥ 1 şartlarını sağlamaya çalışalım. Bu durumda ilk kelimemiz:
s = a1b1c1
olarak yazılacaktır. Bu yazımdan u ve z değerlerinin boş olabileceğini düşünürsek
v= a
x= b
y= c
olarak yazılabilir. Bunun dışındaki şartların hiç birisi s = uvxyz şartını ve s = aibici | i > 0 şartını aynı anda sağlamaz.
Şimdi ilk kelimemizi yazdığımıza göre, kelimemizi pompalayarak çıkan sonuçların yine bu dilde olup olmadığını kontrol edelim:
Yukarıdaki denemede i=1 için yazmıştık, şimdi i=2 için uvxyz değerlerini bulmaya çalışalım.
Böyle bir değer bulunamaz çünkü
s = a2b2c2
değerini ancak
s = uv ixy iz
pompalamasında i=2 yazarak sağlamaya çalışabiliriz ve bu durumda da x değeri olan b değeri 1 tane kalacağı için problem olacaktır. Daha basit bir ifadeyle CFG gösteriminde 3 değerin birden aynı sayıda olması garanti edilemez, ancak iki değer aynı sayıda olabilir. Çünkü yukarıdaki v ve y değerleri pompalandığında artarken x değeri tek değer olarak kalacaktır.
Benzer şekilde
u= a
v=b
y=c
olması durumunda u,
v=a
y=b
z=c
oması durumunda da z değerleri tek kalacak ve diğer harfler pompalanırken dengeyi bozacaktır.
Yukarıdaki durumda L = {aibici | i > 0} dilinin bir CFG gösterimi ile gösterilemeyeceği ispatlanmış olur.