pushdown automaton

• 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.