シラバス
※学期中に内容が変更になることがあります。

2013年度

1G0121-001 

○言語理論－1
－1
2単位/Unit  春学期/Spring  京田辺/Kyotanabe  講義形式

  芳賀　博英

＜概要/Course Content Summary＞

本講義では，オートマトン・正規表現・形式文法について，その基礎的な内容を講義する。最初に有限オートマトンと正規表現について述べ，その後で有限オートマトンと正規表現の等価性について述べる。形式文法では，実用上最も重要な文脈自由文法について，その概念を述べた後，その解析法について述べる．さらに文脈自由文法とプッシュダウンオートマトンの等価性についても解説する．

＜到達目標/Goals,Aims＞

(1) オートマトンと正規表現の概念が理解でき，具体的な問題に応用できるようになる．　
(2) 文脈自由言語の解析法の基礎的な技法を身につけ，基本的な構文解析系のプログラムが書けるようになる．

＜授業計画/Schedule＞

（実施回/
Week） 		（内容/
Contents） 		（授業時間外の学習/
Assignments）
（実施回/ Week） 1  （内容/ Contents） 有限オートマトン  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 2  （内容/ Contents） 正規表現  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 3  （内容/ Contents） 非決定性  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 4  （内容/ Contents） 有限オートマトンと正規表現の等価性  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 5  （内容/ Contents） 有限オートマトン，正規言語の反復補題  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 6  （内容/ Contents） 有限オートマトンと正規表現の応用  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 7  （内容/ Contents） 中間まとめ  （授業時間外の学習/ Assignments） 中間まとめ演習の復習 
（実施回/ Week） 8  （内容/ Contents） 文脈自由文法(CFG)  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 9  （内容/ Contents） ブッシュダウンオートマトン(PDA)，チョムスキー階層  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 10  （内容/ Contents） CFGとPDAの等価性  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 11  （内容/ Contents） チョムスキー標準形，CFGにおける反復補題  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 12  （内容/ Contents） CFGの詳細，導出，下向き構文解析  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 13  （内容/ Contents） 上向き構文解析法  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 14  （内容/ Contents） LR構文解析（その1）  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 
（実施回/ Week） 15  （内容/ Contents） LR構文解析（その2）  （授業時間外の学習/ Assignments） 講義の復習・次回講義の予習 

受講者の理解状況を勘案して，授業計画を変更する可能性がある．

＜成績評価基準/Evaluation Criteria＞

中間筆記試験  50%  オートマトン，正規表現の基礎的な事項の理解度 
期末筆記試験  50%  文法の概念と構文解析法の手法の理解度 

(1) 中間試験，期末試験はいずれも必須です．インターネット講義の受講生も必須です．　
(2) 中間試験は教室講義，インターネット講義の両方のクラスの受講生が全員受講できる日程を設定しますので，通常の講義時間とは異なります．現在の予定では6月1日の土曜日に実施する予定です．ただし，講義の進捗によっては，変更する可能性もあります．ですから，5月下旬から6月中旬までの土曜日の午後にはできるだけ予定を入れないようにしてください．

 

＜成績評価結果/Results of assessment＞   成績評価の見方について/Notes for assessment

    

登録者数

成績評価（%)

評点
平均値

備考
A B C D F 他
43 7.0 14.0 20.9 27.9 30.2 0.0 1.4

＜テキスト/Textbook＞

J. ホップクロフト， J. ウルマン， R. モトワニ， (原著)， 野崎 昭弘， 町田 元， 高橋 正子， 山崎 秀記 (翻訳)  『オートマトン言語理論 計算論〈1〉』第2版  (サイエンス社、2003) ISBN:978-4781910260 

 

＜参考文献/Reference Book＞

米田政明，広瀬貞樹，大里延康，大川知  『オートマトン・言語理論の基礎』(近代科学社、2003)ISBN:978-4764902978 初歩的な内容が平易に記述してある．演習問題の解答が丁寧にされている． 
 

Michael Sipser (著)， 太田和夫，田中圭介，阿部正幸，植田広樹，藤岡 淳，渡辺治(訳)  『計算理論の基礎 [原著第2版]－1.オートマトンと言語－』(共立出版、2008)ISBN:978-4320122079 本格的な教科書．原著を3分冊に分けて翻訳したものの第1分冊． 
 

大川 知， 広瀬 貞樹， 山本 博章   『オートマトン・言語理論入門－未来へつなぐ デジタルシリーズ 5－』(共立出版、2012)ISBN:978-4320123052 標準的な内容を含む教科書 
 

 

 

 
お問合せは同志社大学 各学部・研究科事務室まで
 
Copyright(C) 2013 Doshisha University All Rights Reserved.　無断転載を禁止します。