タイトル

科目番号
情252 
開講年度 期間 曜日時限 開講学部等
2017 前学期 木2 工学部情報工学科  
講義コード 科目名[英文名] 単位数
601316001 言語理論とオートマトン   2 
担当教員[ローマ字表記]
高良 富夫 
授業内容と方法
 自然言語処理やプログラミンング言語の基礎理論となる形式言語理論を中心に、計算ハードウエア理論の基礎となるオートマトンとの関連を中心に学習する。有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語が中心課題である。重要な課題ごとに、理論・例題・演習の繰り返しの形式で行う。
 内容は教科書に沿っており、下の授業計画に教科書の節を示してある。予習や、授業中分からなかったところの復習のために、教科書を有効活用すること。
 
達成目標
有限オートマトンと正規言語、プッシュダウンオートマトンと文脈自由言語に関して、下記の項目における専門用語が示すものの具体的内容及びその有効性,適用範囲を理解すること(専門性[H-2])。これらの基本的問題を操作し解くことができること(実践性[F-1])、例題の少ないところは自ら具体的な例を作り出して考えを進めることができること(問題解決能力と創造性[G-3])
 
評価基準と評価方法
評価基準:以下のことができること。
(1)集合演算。F
(2)ミーリー型順序機械からムーア型順序機械への変換。F
(3)決定性有限オートマトンの動作の実施。F
(4)すべての状態対についての等価性の判定と最簡形の作成。H
(5)非決定性有限オートマトンから決定性有限オートマトンへの等価変換。H
(6)正規文法での導出。F
(7)有限オートマトンと等価な正規文法の構成H
(8)導出の例を作り、導出木を描く。G
(9)ε-生成規則の除去。F
(10)チョムスキーの標準形およびグライバッハの標準形にする。H
(11)プッシュダウンオートマトンの動作を計算状況で示す。F
(12)グライバッハ標準形文脈自由文法と等価なプッシュダウンオートマトンを構成する。H
(13)構文解析H

評価方法:
受講状況(20%),宿題(20%),中間試験(30%),期末試験(30%)によって総合的に評価する。
 
履修条件
情報数学I,IIを履修していることが望ましい。
 
授業計画
第1回(4/13) 言語理論概説、集合論の基礎(1.1, 1.2)
第2回(4/20) 順序機械(2.1)
第3回(4/27) 有限オートマトン(2.2, 2.2.1)
第4回(5/11) 有限オートマトンの等価性の判定(2.2.2, 2.2.3, 2.2.4, 2.2.5)
第5回(5/18) 非決定性有限オートマトン(2.3, 2.3.1)
第6回(5/25) 形式文法(3.1)、正規文法(3.2)
第7回(6/ 1) 正規文法とオートマトン(3.2.1,3.2.2)
第8回(6/ 8) 中間試験 
第9回(6/15) 文脈自由文法(4.1)、導出木(4.2)、あいまい性( 4.3)
第10回(6/22)文脈自由文法の簡単化I(4.4, 4.4.1, 4.4.2)
第11回(6/29) 文脈自由文法の簡単化II(4.4.3)、チョムスキー標準形(4.5, 4.5.1)
第12回(7/ 6) グライバッハ標準形(4.5.2)
第13回(7/13) 非決定性プッシュダウン・オートマトン(4.10)
第14回(7/20) 文脈自由文法とプッシュダウン・オートマトン(4.10.1, 4.10.2)
第15回(7/27) 所属問題と構文解析(4.11, 4.11.1)
第16回(8/ 3) 期末試験
 
事前学習
予習:シラバスを見て教科書の当該部分を読んでおくこと。
 
事後学習
復習:毎回宿題があるので、できれば2日後に課題をこなして、次週必ず提出すること。チェックして次の週に返却するので、添削されたところを復習しておくこと。宿題に3時間以上かかった場合は、その旨レポートに記述すること。
 
教科書にかかわる情報
教科書 書名 ISBN
4627805500
備考
著者名
出版社
出版年
NCID
BA30181677
 
教科書全体備考
 
 
参考書にかかわる情報
 
参考書全体備考
 
 
使用言語
日本語
 
メッセージ
WeBClass:言語理論とオートマトン
ニュースグループ: ura.ie.classes.lang-auto
教科書は各自生協で購入すること。
授業計画に日程と内容が示してあるので、予習復習に活用すること。
 
オフィスアワー
月、木の9:00-10:00 できるだけメールで予約すること。
 
メールアドレス
takara@ie.u-ryukyu.ac.jp
 
URL
https://ie.u-ryukyu.ac.jp/takara/
 

ページの先頭へ