オートマトンと言語理論

オートマトンと言語理論の基礎を学習する． オートマトンとは， 計算の原理を解明するために考案された数学的モデルである． 言語理論とは， プログラミング言語の（文法に関する）数学的モデルである形式言語を扱う理論分野である． オートマトンと形式言語は， それぞれ異なった分野で考案されたモデルであるが， それらの間には密接な関係がある． 本講義では，言語とは何か？，から始め， オートマトンと形式言語，それにそれらの間の関係を学習する．

• テキスト

講義スケジュール

1. 導入（言語とは，言語理論とは，オートマトンとは）
2. 正規表現
3. 有限オートマトン１（決定性有限オートマトン）
4. 有限オートマトン２（非決定性有限オートマトン）
5. 有限オートマトン３（ＤＦＡとＮＦＡの等価性）
6. 有限オートマトン４（非正規言語）
7. 演習１
8. 到達度確認テスト１
9. 文脈自由文法１（文脈自由文法と文脈自由言語）
10. 文脈自由文法２（導出木）
11. プッシュダウンオートマトン１（非決定性プッシュダウンオートマトン）
12. プッシュダウンオートマトン２（非文脈自由言語）
13. 演習２
14. 到達度確認テスト２