pumping lemma

• üçüncü kez aldığım sikindirik otomata teorisi dersinin sikindirik teorisi. "s = xyz olsun, şöyle şöyle sebeplerden ötürü y budur, y'yi şöyle güzelce pump etsek bulduğumuz string bu language'de olamaz demek ki regular değil" şeklinde götüm gibi bir kanıtlama yöntemi vardır. ben öyle proof by contradiction'ın amına koyayım. öf. ^*
• formal languages and automata theory dersi dahilinde bir dilin düzensiz olduğunu göstermekte kullanılan bir yöntemdir..biraz önce çalıştım ordan biliyorum..
• "formal languages and automata theory" dersinin vizesinde denk gelirseniz nasıl "pump" edildiğinden şüpheniz kalmayacak lemmadır. p, bir diğer deyişle pumping length, dersin hocasına göre değişir.
• asiri soyut olmasi sebebiyle ilk etapta beyinde cesitli error'lara sebep olmasi ile unludur. mesela bizim hoca bir arkadasa 5 dk boyunca xyz stringindeki y'nin uzunlugu ile ilgili assumption yapmamasi gerektigini anlatmaya calismisti.
  
  ispatini okuyup anladiktan sonra ise bu error'lar yerini kelebeklere, gokkusaklarina birakir. insanoglunun zekasina bir kez daha hayran kalirsiniz.
• bunu anlamadan mezun oldugum icin cok mutluyum. eger cs buysa ben de cs'ci falan degilim lan gercekten.
  
  cs'te ogrendigim "yok la bu heralde isime yaramaz ama aklimda tutayim" diye tuttugum ww/rw/rr conflict detection'dan tut digraph cycle detection'a kadar ilginc seyleri mezun olduktan sonra 3 ay icinde kullanma imkani buldum. ama insallah bu serefsizle bi daha karsilasmayiz. cehennemin dibine kadar yolun var dostum (insallah pumping lemma diye bi adam yoktur^*)
• üniversitede lise mantığa geri dönüş yaptırır bu teorem. nasıl mı? hani lisede zor konularda ilk önce formül verilir çözülmesi gereken sorular bu formül yardımı ile çözülür daha sonra ise formülün nerden geldiği anlatılır. tabi bu arada akıla bir çok soru takılır, bu değişken nerden geliyordu, bunun neden bilmem kaçıncı dereceden üstü alındı falan diye. işte bu pumping lemma'da aynen böyle anlatılır. zaten soyut olan bir dersin gayet soyut bir teoremi olan pumping lemma lise mantığıyla anlatıldığında xyz nerden çıktı, ne kadar pump ediyoruz^*gibi soruları beraberine getirir. ayrıca teorem olarak nitelendiremeyiz galiba bunu adı üstünde lemma.
• bir dilin regüler olmadığını olmayana yergi yöntemi(by contradiction) ispatlayan bir yöntemdir.temelde çok basit 1 koltuğa iki karpuz sığmaz( pigeon hole principle) prensibine dayanmasına karşın matematiksel ifadelerde olay hallaç pamuğuna döner.
  
  yapılan iş regüler olduğu iddia edilen dilin olası şişirilmiş varyasyon kelimelerinin hepsinin bir regüler dile ait olmadığını ispatlayarak sonuca ulaşmayı hedefler.
  
  önemli kısım ,yöntem dilin regülerliğini ispatlamaz,dilin regüler olmadığını ispatlar.
• temelde pigeon hole principle ve proof by contradiction kullanan güzide bir yöntem...
  
  (bkz: i am the pompacı)
• bu aralar en bi nefret ettiğim hede. regular languages için olanı yetmiyormuş gibi bir de şu an context-free languages için olanla uğraşıyorum lanet formal languages dersi için.
• iki kere university of freiburgda iki kere dokuz eylul universitesinden aldigim computer science theory ya da theory of computation ya da automata and formal languages derslerinin dunyalar sacmasi teorisi. yok neymis dilin regular olmadigi ispatlaniyormus ama regular oldugundan emin degilmis. yok al stringi, bol x, y ve z'ye sonra y'yi pump ya da down et. bak bakalim olusturdugun string dalen dilin icinde mi? bir de bunun context-free languages icin olani var dusman basina.
  gelecek sinav icin taktigim, dersin sinavlari zaten open source. tum sorulari bulup yapistiririm artik cevabi ne yapayim.