pushdown automaton ^*

• iki stack kullanabilen p.d.a. tek stackli pda'dan daha güçlüdür, ama üç stackli pda iki stackli pda'dan daha güçlü değildir.
• üstten bastırmalı makine^* . iki stackli pushdown automaton bir turing machine kadar güçlüdür, zaten daha güçlüsü de yoktur.
• iki stack yerine tek bir queue ile de turing machine kadar güçlü olur. yani bunu bulan adam dur lan şuna stack değil de queue koysak noluyo acaba deseymiş bugün belki de turing machine değil osman machine kavramı bilgisayar biliminde yerini alacaktı.
• bağlamdan bağımsız^* tüm dilleri tanıyan bir sonlu durum makinesi^* yapılamaz. bu dili^* tanıyabilen bir otomatın bellek elemanının olması gereklidir. bu şekilde elde edilen makine, bağlamdan bağımsız her dili tanıyabilir. bellek elemanı olarak içinde kullanılan "yığın^*" kavramından ötürü, ismini "üstten bastırmalı makine" yerine "yığın yapılı otomat" olarak türkçeleştirirsek daha güzel olur sanki.
• her context free grammar'ın dengi bir pushdown automaton vardır. bunu gösterirken nondeterminism'den dibine kadar faydalanırlar. baya basittir olay.
  
  3 state çizilir : başlangıç, döngü, kabul state'leri olmak üzere.
  
  döngü state'i işin kalbidir. o state'te değişkenler, değişkenler ve terminallere dönüştürülür. mümkün olabilecek tüm dönüşümler nondeterministik olarak ifade edilir. yığın^*'ın en tepesinde ne varsa ona göre yapılır dönüşümler. eğer yığının tepesinde terminaller varsa hemen okunur ve ondan artık kurtulunur. neden okunur? parse tree'yi hayal edin. o okuyacağımız terminal kullanılarak herhangi bir dönüşüm yapılamaz. o terminal tam oraya çivili. ilelebet orada kalacak, sırası (string index) değişmeyecek yani.
  
  bu okuma işleminden sağ çıkan dönüşümlerin herhangi birinin yığını boşsa hemen kabul state'ine girer. böylece pushdown automaton kabul eder bu string'i.
  
  valla böyle çok anlaşılır oldu mu bilmiyorum. michael sipser'ın kitabı baya güzel bir kaynak computation theory için.
• finite automata ya da finite state machine denen zımbırtının sadece regular dilleri kabul ettiği gibi, pushdown automata da context free dilleri kabul eder. tüm regular dillerin aynı zamanda context free de olduğunu da göz önünde bulundurursak, pushdown automata hem regular hem de context free dilleri kabul ya da reddedebilen, finite state machine'den daha gelişmiş bir makinedir.
  
  pushdown automata'yı finite automata'dan ayıran en büyük özellik sahip olduğu ekstra hafıza, stacktir. örnek vermek gerekecek olursa (a^n)(b^n) şeklinde tanımlanan bir dil regular değildir, çünkü hiçbir dfa ya da nfa olması farketmeksizin hiçbir finite automata n sayısını hafızasında tutup a ve b'nin aynı sayıda n içerip içermediğini kontrol edebilecek kadar gelişmiş değildir. (a^n)(b^n) context freedir, çünkü bu dil için bir pda yaratılabilir. pda'ler sahip olduğu stack sayesinde karşısına çıkan her a'yı stack'te depolayarak, yine karşısına çıkan her b için bir a'yı stack'ten çıkarak input string üzerinde işlemediği karakter kalana kadar bu döngüye devam eder. eğer input string üzerindeki tüm karakterler işlendikten sonra stackte hiçbir karakter kalmadıysa, ya da sadece stack'in sonu olduğunu belirten pda sembolü (genelde z, z0 veya $) kaldıysa bu stringin context free olduğunu, aksi takdirde de context free olmadığını belirtir.