【シプサ】2 文脈自由言語

こつこつ。

• 引き続き、計算理論において何故「言語」をやらなければいけないのかが理解できていない。それはそれで楽しいし、コンパイラとかに役立ちそうだからやるのはいいんだけど。それが「計算」とどう関係しているかはまだわからない。
  
• おそらく、第二巻以降で計算を考えていくときのツールになるのだろうと予測して、できるだけ慣れておくようにしたい。
  
• 文脈自由文法(CFG)の定義を知った。BNF記法とかいわれているものと同じ表記かな?
  
• プッシュダウン・オートマトン(PDA)の定義を知った。
  
• 構文解析木(parse tree)が意味を与える、ということがわからない。parse treeの構造が複数存在したって意味は同じということだってあるんじゃないの？ また、girl とか boy の意味はどこであたえられるのか? 述語 love や 前置詞 with の意味はどこであたえられるのか。それらの意味があたえられていれば、文の parse tree がひとつに定まったとき、その文を一通りに解釈することはできる。その構造はCFGによって定義されている、ということもわかる。しかし、だ。
  
• 意味という言葉自体の曖昧さが、元凶と思われるのだが。。。
  

次回は、CFGが記述できる言語クラスとPDAが記述できる言語クラスが等価であることの探求から。