【シプサ】2 文脈自由言語 (その3)

PDAがしっくりこないのがくやしくて、ねばってみた。

• 言語{0^n1^n|n>=0}のPDA(例2.14)を調べてみた。
  
• わからなさの根源は、PDAの定義の理解にあることがわかった。(やった！)
  
• というのはPDAの定義は、定義というより「諸元表記法」というニュアンスがあり、PDAの動作の仕組みは、それの計算というか受理方法にあったからだ(受理を考えるときに、文字列の列が出てきて、それがスタックの記憶域を実現している)。それはPDAの定義には含まれていない。だけどその計算方法が前提となっていれば、PDAの定義と言われるものを指定すれば、たしかにPDAの振舞はきまるから定義されるといえる。だから諸元的。
  
• そしてPDAの遷移関数は、スタックについて言うと、その文字列の先頭の置換を定義している。
  
• ミソは置換の際に、空列をうまくつかっていることだ。すなわち、空列から文字への遷移は、スタック文字列の先頭に空列がひとつあるとして、それを文字へ置換することによって「スタックへのpush」を表現している。逆に文字から空列への遷移はpopを表現している。
  
• あー、すっきりした。これで眠れる。
  

じわじわ。