有限オートマトンと言語理論

科目基礎情報

学校 沼津工業高等専門学校 開講年度 令和04年度 (2022年度)
授業科目 有限オートマトンと言語理論
科目番号 2022-725 科目区分 専門 / 選択
授業形態 授業 単位の種別と単位数 学修単位: 2
開設学科 環境エネルギー工学コース 対象学年 専2
開設期 後期 週時間数 2
教科書/教材 教員作成の独自教材を利用する
担当教員 鈴木 康人

到達目標

1.形式言語と形式言語に関わる基本的な定義や概念について他人に説明できる(B1-4)
2.正規文法やオートマトンによって正規言語を正しく定義できる
3.文脈自由文法やプッシュダウン・オートマトンによって文脈自由言語を正しく定義できる
4.再帰的数え上げ可能言語に対応するチューリング機械 (= 狭義のアルゴリズム ) が与えられたとき 、与えられた語が受理されるか、されないかを追跡できる

ルーブリック

理想的な到達レベルの目安(優/良)標準的な到達レベルの目安(可)未到達レベルの目安
形式言語と形式言語に関わる基本的な定義や概念について他人に説明できる(B1-4)□形式言語と形式言語に関わる基本的な定義や概念について他人に説明できる□形式言語と形式言語に関わる基本的な定義や概念について他人に説明できない
正規文法やオートマトンと関連させて正規言語を正しく定義できる□可の基準に加えて正規言語で表現できない言語が存在することをポンプの補題で証明できる□正規文法やオートマトンによって正規言語を正しく定義できる□正規文法やオートマトンによって正規言語を正しく定義できない
文脈自由文法やプッシュダウン・オートマトンと関連させて文脈自由言語を正しく定義できる□可の基準に加えて文脈自由言語で表現できない言語が存在することをポンプの補題で証明できる□文脈自由文法やプッシュダウン・オートマトンによって文脈自由言語を正しく定義できる□文脈自由文法やプッシュダウン・オートマトンによって文脈自由言語を正しく定義できない
チューリング機械による言語の定義を理解できる□可の基準に加えて再帰的数え上げ可能言語が与えられたとき , そのアルゴリズムを正しく表記できる□再帰的数え上げ可能言語に対応するチューリング機械 (= 狭義のアルゴリズム ) が与えられたとき , 与えられた語が受理されるか , されないかを追跡できる□再帰的数え上げ可能言語に対応するチューリング機械 (= 狭義のアルゴリズム ) が与えられたとき , 与えられた語が受理されるか , されないかを追跡できない

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

実践指針 (B1) 説明 閉じる
実践指針のレベル (B1-4) 説明 閉じる
【プログラム学習・教育目標 】 B 説明 閉じる

教育方法等

概要:
計算機の数学モデルであるチューリング機械について構成要素と働き、動作を表記でき、計算機の理論上の限界を理解できる。
授業の進め方・方法:
座学による講義での授業。適宜、授業の前に自筆ノート参照可とする小試験を実施する。この小試験を持ってノート検査に換える。
注意点:
評価については、評価割合に従って行います。
集合や数学的帰納法などに基づく議論を展開することがあり、本校の他の講義と異なる種類の数学を扱うため、慣れていないと不合格となることがあります。

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

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

授業計画

授業内容 週ごとの到達目標
後期
3rdQ
1週 オリエンテーション 講義内容概説
2週 述語論理式の導入 述語論理式について理解し表現できる
3週 形式言語、正規言語(1) 直積集合や冪集合について理解し利用できる、形式言語とその周辺の専門用語について理解し利用できる、オートマトンの定義を理解できる
4週 正規言語(2) 正規表現を理解し利用できる、非決定性有限オートマトン(NFA)を書くことが出来る、NFAの構造表記を理解し利用できる
5週 正規言語(3) DFAと正規表現の等価性を説明できる
6週 正規言語(4) 鳩の巣原理について理解できる、ポンプの補題を用いて非正規言語が正規言語ではないことを証明できる
7週 文脈自由言語(1) 文脈自由文法(CFG)を書くことが出来る、チョムスキー標準形を理解し利用できる
8週 文脈自由言語(2) プッシュダウン・オートマトン(PDA)を書くことが出来る、CFGとPDAの等価性を理解できる、DPDAとNPDAの違いを説明できる
4thQ
9週 文脈自由言語(3)/再帰的数え上げ可能言語(1) CFGの扱える言語とPDAが扱える言語の範囲が等価であることを理解できる、チューリング機械(TM)を書くことが出来る
10週 再帰的数え上げ可能言語(2) 再帰的数え上げ可能言語の定義を説明できる、TMの頑健性について理解できる、チャーチ・チューリングの提唱について説明できる
11週 再帰的数え上げ可能言語(3) TMによる正規言語の等価性判定や空性検査について理解できる、TMによるCFLの等価性判定や空性検査について理解できる、万能TMについて説明できる
12週 再帰的数え上げ可能言語(4) 再帰的数え上げ可能ではない言語が存在することを説明できる
13週 再帰的数え上げ可能言語(5) 計算量について定義を理解できる
14週 再帰的数え上げ可能言語(6) TMの時間計算量と空間計算量に対する線形圧縮定理を理解できる、NP完全性を理解できる
15週 最近の話題 形式言語理論における最近の動向について説明する
16週

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週

評価割合

試験ノート検査その他合計
総合評価割合80200100
形式言語と形式言語に関わる基本的な定義や概念について他人に説明できる(B1-4)2010030
正規文法やオートマトンと関連させて正規言語を正しく定義できる205025
文脈自由文法やプッシュダウン・オートマトンと関連させて文脈自由言語を正しく定義できる205025
チューリング機械による言語の定義を理解できる200020