数理論理学と同様、こちらも雲行きが怪しくなる。いわゆる証明のお話でかなり抽象度が高い。
抽象度が高いというのは、様々な場合を考えてそれをある形に置き換え、お話をするため、その置き換えが頭の中で瞬時にできないと戸惑ってしまう。とても簡単なお話であったとしても。
まずはプッシュダウンオートマトン（ＰＤＡ）と文脈自由言語との関係について。つまり文脈自由言語はプッシュダウンオートマトンによって必ず受理できるかどうかという証明である。延々と帰納法が続き、途中でわけわかに・・・。後で復習しなければ。
ちなみに逆も言えるようだが、もう何も考えずにノートをとっていました。すいませんです。
で、最後にちょっとだけ決定性ＰＤＡについて。ここは定理だけ。まぁ、いいやって感じでした。
