【東工大院試用】オートマトン・数理論理学のまとめ

東工大の院試対策の際、自分の復習用に作っていたオートマトンと数理論理学のまとめを公開します。
オートマトンは問題と簡単な解答(もしくはその方針)を書いており、網羅性は高く全ての問題に答えられれば理解度は十分と言えると思います。
数理論理学は資料の気になるところを箇条書きしたのみで、網羅性は高くないです。また、試験ではここまで細かいことを聞かれることはないと思うので知識の抜けを減らしたい人が最後の確認に使える程度のものだと思います。また、数理論理学に関しては特に記述の正確性に自信がありません。
オートマトン・数理論理学ともに自分の知識の確認のために書いたものなので記述はあまり丁寧ではなく、間違っている可能性もあるのでこれを使って１から勉強することはできないと思いますが、参考程度にどうぞ。

オートマトン

正規言語に関する問題

1. 句構造文法を定義する際、何が必要

2. 正規文法の生成規則の形は？

3. 正規言語の和集合を作るには？

4. 正規言語の連接を作るには？

5. 正規言語のクリーネ閉包を作るには？

6. 有限オートマトンを定義する際、何が必要

7. ε遷移を除去するには？

8. 補集合を受理するには？

9. 和集合を受理するには？