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

科目基礎情報

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

到達目標

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

ルーブリック

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

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

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

教育方法等

概要:
計算機の数学モデルであるチューリング機械について解説し、計算機の理論上の限界を学ぶための基礎を学習する。
授業の進め方・方法:
座学による講義での授業。適宜、授業の前に自筆ノート参照可とする小試験を実施する。この小試験を持ってノート検査に換える。
注意点:
1.試験や課題レポート等は、JABEE 、大学評価・学位授与機構、文部科学省の教育実施検査に使用することがあります。
2.授業参観される教員は当該授業が行われる少なくとも1週間前に教科目担当教員へ連絡してください。

授業計画

授業内容 週ごとの到達目標
前期
1stQ
1週 オリエンテーション 講義内容概説
2週 形式言語、アルファベット、正規表現 形式言語を説明できる、アルファベットを説明できる、正規表現から該当する言語に属する/属さない元を判断できる
3週 正規言語(1) 決定性有限オートマトン(DFA)を書くことが出来る
4週 正規言語(2) 非決定性有限オートマトン(NFA)を書くことが出来る
5週 正規言語(3) DFAとNFA、正規表現の等価性を説明できる
6週 正規言語(4) ポンプの補題を用いて非正規言語が正規言語ではないことを証明できる
7週 文脈自由言語(1) 文脈自由文法(CFG)を書くことが出来る
8週 文脈自由言語(2) プッシュダウン・オートマトンを書くことが出来る
2ndQ
9週 文脈自由言語(3) CFGの扱える言語とPDAが扱える言語の範囲が等価であることを理解できる
10週 文脈自由言語(4) CFGの扱える言語とPDAが扱える言語の範囲が等価であることを説明できる
11週 文脈自由言語(5) ポンプの補題を用いて非文脈自由言語が文脈自由言語ではないことを証明できる
12週 再帰的数え上げ可能言語(1) チューリング機械(TM)を書くことが出来る
13週 再帰的数え上げ可能言語(2) TMの動作を表現できる、アルゴリズムとチャーチ・チューリングの提唱を説明できる
14週 再帰的数え上げ可能言語(3) 再帰的数え上げ可能ではない言語が存在することを説明できる
15週 プログラムの評価 時間計算量、決定可能性、停止性などの概念を理解し説明できる
16週

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

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

評価割合

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