授業の主題
|
|
|
|
言語の形式的な記述と，そのように記述された言語の認識が本科目の主題である．これらはプログラミング言語やコンパイラの設計，テキスト処理といった言語処理技術の基礎である．本授業では特に，プログラミング言語のトークンの表現と認識を扱う．
|
| |
|
|
学修目標（到達目標）
|
|
|
|
言語の数学的モデルである形式言語について，生成規則(文法)と認識機械(オートマトン)の二つの側面から学ぶ．特に，プログラミング言語のトークンを表現する能力を持つ正規表現と，それらを認識する能力を持つ有限オートマトンについて理解することを目指す．
|
| |
|
|
|
|
|
|
授業概要
|
|
|
1. 準備(2回): 集合，写像，証明
2. 正規表現(2回): 文字列，言語，正規表現
3. 有限オートマトン(4回): 決定性有限オートマトン(DFA)，非決定性有限オートマトン(NFA)，正規表現のNFAへの変換，NFAのDFAへの変換，DFAの最小化，正規表現とDFAの等価性
4. 期末試験
|
| |
|
|
評価方法と割合
|
|
評価方法
|
|
|
次項の項目及び割合で総合評価し、次のとおり判定する。
「Ｓ（達成度90％～100％）」、「Ａ（同80％～90％未満）」、
「Ｂ（同70％～80％未満）」、「Ｃ（同60％～70％未満）」を合格とし、
「不可（同60％未満）」を不合格とする。（標準評価方法）
|
| |
|
|
|
|
|
|
授業時間外の学修に関する指示
|
|
予習に関する指示
|
|
|
|
次回の講義内容について配布プリントを読んでくること．
|
| |
|
予習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
復習に関する指示
|
|
|
|
講義のあった当日に再度配布プリント・ノートにて復習すること．
|
| |
|
復習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
教科書・参考書
|
|
参考書
|
|
|
|
|
978-4-320-12207-9
|
|
Michael Sipser著 ; 阿部正幸 [ほか] 訳
|
|
共立出版
|
2008
|
|
|
|
4-7819-1026-2
|
|
J. ホップクロフト, R. モトワニ, J. ウルマン共著 ; 野崎昭弘 [ほか] 共訳
|
|
サイエンス社
|
2003
|
|
|
|
4-7819-1027-0
|
|
J. ホップクロフト, R. モトワニ, J. ウルマン共著 ; 野崎昭弘 [ほか] 共訳
|
|
サイエンス社
|
2003
|
|
|
|
|
|
|
オフィスアワー等（学生からの質問への対応方法等）
|
|
|
|
電子メールで受け付ける．
|
| |
|
|
履修条件
|
|
|
|
|
|
|
|
|
|
|
その他履修上の注意事項や学習上の助言
|
|
|
|
配布プリントは，教科書というよりはノートであり，必ずしもこれだけを読んで学べるようには書かれていない．授業内容と併せて初めて役に立つものであるので，この点を十分意識して授業に臨まれたい．
|
| |
|
|
|
|
カリキュラムの中の位置づけ
|
|
|
|
本科目は「形式言語論とオートマトンB」「コンパイラ」の基礎である．
|
| |
|
|
|
|
|