オートマトンと言語理論
オートマトンと言語理論の基礎を学習する.
オートマトンとは,
計算の原理を解明するために考案された数学的モデルである.
言語理論とは,
プログラミング言語の(文法に関する)数学的モデルである形式言語を扱う理論分野である.
オートマトンと形式言語は,
それぞれ異なった分野で考案されたモデルであるが,
それらの間には密接な関係がある.
本講義では,言語とは何か?,から始め,
オートマトンと形式言語,それにそれらの間の関係を学習する.
講義スケジュール
- 導入(言語とは,言語理論とは,オートマトンとは)
- 正規表現
- 有限オートマトン1(決定性有限オートマトン)
- 有限オートマトン2(非決定性有限オートマトン)
- 有限オートマトン3(DFAとNFAの等価性)
- 有限オートマトン4(非正規言語)
- 演習1
- 到達度確認テスト1
- 文脈自由文法1(文脈自由文法と文脈自由言語)
- 文脈自由文法2(導出木)
- プッシュダウンオートマトン1(非決定性プッシュダウンオートマトン)
- プッシュダウンオートマトン2(非文脈自由言語)
- 演習2
- 到達度確認テスト2
Last Update: 01/September/2020