構文木によって導出される言語は最左導出によって得られる言語とのクラスは一致するというお話の証明。次に、パーサーについての簡単な説明がある。これは、コンパイラなどで使用されている文解析に関する仕組みが文脈自由言語の導出に基づいていることの紹介である。
次に、文法の曖昧さについて。これは、構文木がいくつかの種類について考えられる場合を示している。また、本質的に曖昧な言語が存在するというお話。しかし、これはよく考えないとほんとうにそうなのか、話を聞いているだけではわからなかった。
最後にプッシュダウンオートマトンについて簡単に。だんだんチューリングマシンに近づいてきたことがよくわかる。
ところで、先生の余談で「自明である」という証明がわからなくて本当にこの仕事でご飯が食べていけるのか心配になったというお話があった。で、自分が実際に本を書くようになるとその気持ちがよくわかるようになったという。いちいちそこまで書いているとあまりに長すぎる場合は、やっぱり「自明である」としたいらしい。
たしかに。
