言語理論

科目基礎情報

学校 岐阜工業高等専門学校 開講年度 令和03年度 (2021年度)
授業科目 言語理論
科目番号 0084 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 1
開設学科 電気情報工学科 対象学年 4
開設期 後期 週時間数 後期:2
教科書/教材 オートマトン・言語と計算理論(岩間一雄・コロナ社)
担当教員 出口 利憲

目的・到達目標

以下の各項目を到達目標とする
(1) 計算機のモデルを理解する。
(2) 形式文法を理解する。
(3) 計算機のモデルと形式文法の関係を理解する。
(4) 抽象的思考ができる。
岐阜高専ディプロマポリシー:(D)

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解し,構築することができる有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解している有限オートマトン,プッシュダウ ンオートマトン,チューリング機械を理解していない
評価項目2正規表現,文脈自由文法を理解し,作成することができる正規表現,文脈自由文法を理解している正規表現,文脈自由文法を理解していない
評価項目3オートマトンと形式文法の関係を理解し,互いに変換できるオートマトンと形式文法の関係を理解しているオートマトンと形式文法の関係を理解していない
オートマトン,チューリング機械,形式文法についての証明がわかり,応用できるオートマトン,チューリング機械,形式文法についての証明がわかるオートマトン,チューリング機械,形式文法についての証明がわからない

学科の到達目標項目との関係

教育方法等

概要:
計算機科学の基礎となる形式言語とオート マトンの考え方を理解する。
授業の進め方と授業内容・方法:
教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。
英語導入計画:Technical terms
注意点:
演習には積極的に取り組み,指定された課題を提出すること。
授業の内容を確実に身につけるために、予習・復習が必須である。

授業の属性・履修上の区分

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

授業内容・方法 週ごとの到達目標
後期
3rdQ
1週 言語とは
(AL のレベル C)
言語とは,を理解する
2週 形式言語
(AL のレベル C)
形式言語を理解する
3週 正規表現
(AL のレベル C)
正規表現を理解する
4週 有限オートマトン
(AL のレベル B)
有限オートマトンを理解する
5週 非決定性有限オートマトン(AL のレベル C)
直積を理解する
非決定性有限オートマトンを理解する
6週 有限オートマトンと正規表現
(AL のレベル C)
有限オートマトンと正規表現の関係を理解する
7週 文脈自由文法
(AL のレベル C)
文脈自由文法を理解する
8週 中間試験 これまでの理解が不十分な点を復習し理解する
4thQ
9週 文脈自由文法の標準形
(AL のレベル C)
文脈自由文法の標準形を理解する
10週 プッシュダウンオートマトン
(AL のレベル C)
プシュダウントートマトンを理解する
11週 状態数1のプッシュダウンオートマトン
(AL のレベル C)
状態数を1にできることを理解する
12週 プッシュダウンオートマトンと文脈自由文法
(AL のレベル C)
プッシュダウンオートマトンと文脈自由文法の関係を理解する
13週 チューリング機械
(AL のレベル C)
チューリング機械を理解する
14週 チューリング機械の停止性
(AL のレベル C)
チューリング機械の停止性を覚える
15週 NP 完全問題 NP完全問題を覚える。
言語理論の理解が不十分な点を復習し理解する
16週

評価割合

試験課題合計
総合評価割合20050250
得点20050250