Wed, 10 Sep 2008

weblog

今日の本

  • 計算理論の基礎
    • CFG*1とPDA*2の等価性
    • ポンピング補題の証明
      • なぜb>=2と仮定できるのか不明(P.128)
        • わかった。b=1だと、言語内の任意の文字列は長さが1なので、ポンピング長を2にすれば自明なので。
        • 考察。こちらのパワポの資料のように、ポンピング長をb^{|V|+1}+1の方が、b=1を気にしなくていいのですっきりするかも？

*1:context-free grammar

*2:pushdown automaton