オートマトンと言語理論

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

• シラバス
• 講義資料

講義スケジュール

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