| ■授業内容と方法 |
自然言語処理やプログラミンング言語の基礎理論となる形式言語理論を中心に、計算ハードウエア理論の基礎となるオートマトンとの関連を中心に学習する。有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語が中心課題である。重要な課題ごとに、理論・例題・演習の繰り返しの形式で行う。
内容は教科書に沿っており、下の授業計画に教科書の節を示してある。予習や、授業中分からなかったところの復習のために、教科書を有効活用すること。
|
| ■達成目標 |
有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語に関して、下記の項目における専門用語が示すものの具体的内容及びその有効性，適用範囲を理解すること（専門性[H-2]）。これらの基本的問題を操作し解くことができること（実践性[F-1]）、例題の少ないところは自ら具体的な例を作り出して考えを進めることができること（問題解決能力と創造性[G-3]）
|
| ■評価基準と評価方法 |
評価基準：以下のことができること。
（１）集合演算。F
（２）ミーリー型順序機械からムーア型順序機械への変換。F
（３）決定性有限オートマトンの動作の実施。F
（４）すべての状態対についての等価性の判定と最簡形の作成。H
（５）非決定性有限オートマトンから決定性有限オートマトンへの等価変換。H
（６）ε-動作のある有限オートマトンからε-なし非決定性有限オートマトンへの等価変換H
（７）正規文法での導出。F
（８）有限オートマトンと等価な正規文法の構成H
（９）導出の例を作り、導出木を描く。G
（１０）ε-生成規則の除去。F
（１１）チョムスキーの標準形およびグライバッハの標準形にする。H
（１２）プッシュダウンオートマトンの動作を計算状況で示す。F
（１３）グライバッハ標準形文脈自由文法と等価なプッシュダウンオートマトンを構成する。H
評価方法：
受講状況(20%)，宿題(20%)，中間試験(30%)，期末試験(30%)によって総合的に評価する。
|
| ■履修条件 |
|
情報数学I,IIを履修していることが望ましい。
|
| ■授業計画 |
第1回(4/14) 言語理論概説、集合論の基礎(1.1, 1.2)
第2回(4/21) 順序機械(2.1)
第3回(4/28) 有限オートマトン(2.2, 2.2.1)
第4回(5/12) 有限オートマトンの等価性の判定(2.2.2, 2.2.3, 2.2.4, 2.2.5)
第5回(5/19) 非決定性有限オートマトン(2.3, 2.3.1)
第6回(5/26) ε-遷移を持つ非決定性有限オートマトン(2.3.2)
第7回(6/ 2) 形式文法(3.1)、正規文法(3.2)
第8回(6/ 9) 正規文法とオートマトン(3.2.1,3.2.2)
第9回(6/16) 中間試験
第10回(6/30) 文脈自由文法(4.1)、導出木(4.2)、あいまい性( 4.3)
第11回(7/4(月)) 文脈自由文法の簡単化I(4.4, 4.4.1, 4.4.2)
第12回(7/ 7) 文脈自由文法の簡単化II(4.4.3)、チョムスキー標準形(4.5, 4.5.1)
第13回(7/14) グライバッハ標準形(4.5.2)
第14回(7/21) 非決定性プッシュダウン・オートマトン(4.10)
第15回(7/28) 文脈自由文法とプッシュダウン・オートマトン(4.10.1, 4.10.2)
第16回(8/ 4) 期末試験
|
| ■事前・事後学習 |
予習：シラバスを見て教科書の当該部分を読んでおくこと。
復習：毎回宿題があるので、できれば2日後に課題をこなして、次週必ず提出すること。チェックして次の週に返却するので、添削されたところを復習しておくこと。宿題に3時間以上かかった場合は、その旨レポートに記述すること。
|
| ■教科書 |
ISBN |
|
富田悦次，横森 貴「オートマトン・言語理論」，森北出版
|
4627805500 |
|
| ■参考書 |
ISBN |
|
|
| ■備考(メッセージ) |
WeBClass:言語理論とオートマトン
ニュースグループ: ura.ie.classes.lang-auto
教科書は各自生協で購入すること。
授業計画に日程と内容が示してあるので、予習復習に活用すること。
|
| ■オフィスアワー |
|
月、木の9:00-10:00 できるだけメールで予約すること。
|
| ■メールアドレス |
takara@ie.u-ryukyu.ac.jp
|
| ■URL |
|
http://www.iip.ie.u-ryukyu.ac.jp/iip/takara.html (stoped)
|