| 科目名 |
オートマトンと形式言語 |
| 担当教員 |
坂本 明雄 |
| 対象学年 |
2年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０６ |
開講学期 |
１学期 |
| 曜日・時限 |
月４,木４ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
【 授業の目的 】
オートマトンは，コンピュータの基本的な動作を数学的にモデル化したものである。もっとも単純な構造の有限オートマトンから出発し，その機能を拡張していくとさまざまな計算モデルを作ることができる。この授業では，今日のアルゴリズムや計算に関する理論の基礎となっているチューリング機械と呼ばれる計算機構にまで拡張していく過程を学習する。
一方，形式文法と呼ばれる一定の約束にしたがって生成することができる記号列の集合を形式言語という。一つの形式文法によって一つの形式言語が生成されることになり，その意味で形式文法を「言語の生成装置」とみることができる。これに対して，前述の計算モデルは与えられた記号列が特定の形式言語の要素として含まれるかどうかを識別する「言語の識別機械」と考えることができる。
この授業では，形式言語を識別する機械（計算モデル）と生成する装置（形式文法）の関係を理解することを主たる目的としている。また，チューリング機械を計算のモデルと捉えて，計算の複雑さに関する基本的な概念を理解することを第二の目的とする。
|
| 授業の詳細2 |
【 授業の進め方 】
オートマトンと形式言語を理解するために必要となる数学的な道具として，集合と関数（写像）の概念は重要であり，授業の最初にこれらの概念を具体例を通して学習する。
次に，有限オートマトン，プッシュダウンオートマトン，チューリング機械についてその動作原理を学習する。
後半では，形式言語を生成する装置としての形式文法について，改めてその定義を理解し，正規文法を始めとするさまざまな文法と前半で学んだ計算モデルとの関係を学習する。最後に，計算の複雑さに関する基本的な考え方を学習する。
この授業では，毎回の講義の最後に Quiz（小テスト）を実施してその日の学習内容を復習する。
|
| 授業の詳細3 |
【 達成目標 】
言語の識別機械：有限オートマトン，プッシュダウンオートマトン，チューリング機械の定義を理解し，与えられた機械がどのような形式言語を識別するかを示すことができる。また，基本的な形式言語を識別する機械を構成できる。
言語の生成装置：正規言語や文脈自由言語を生成する文法の定義を理解し，与えられた文法がどのような形式言語を生成するかを示すことができる。また，基本的な形式言語を生成する文法を構成できる。
計算の複雑さ：計算の複雑さに関する基本的な概念を説明できる。
|
| 授業の詳細4 |
【 授業計画（前半）】
１．『オートマトンと形式言語』で学ぶこと
形式言語とはどのようなものかを具体的な例をとおして考える。また，言語の識別機械，生成装置とはどのようなものかを簡単な具体例から理解し，この授業で学ぶ内容を「大体わかった」と思えるようにする。この授業科目の成績評価法についても説明する。
２．集合と関数
オートマトンと形式言語を学ぶための準備として，集合と関数（写像）の概念を復習する。これらの内容は，『情報代数』および『離散数学』で既に学んでいるものである。
３・４．有限オートマトン
言語の識別機械としてもっとも単純な有限オートマトンについて学ぶ。また，有限オートマトンによって受理される語と拒否される語があることから，言語の識別機械としての機能を理解する。
また，有限オートマトンを状態遷移図というラベル付き有向グラフで表現できることを学ぶ。
５・６．さまざまな有限オートマトン
有限オートマトンを拡張した非決定性有限オートマトンなど，有限オートマトンに関するいくつかの話題を学習し，最後に，有限オートマトンでは識別できない言語があることを理解する。
７．有限オートマトンの復習と試験
＊ 有限オートマトンの定義と動作を確実に理解できているかどうかを試験によって確認する。
＊ 試験問題は，授業に使用するテキストにある演習問題のレベルとする。
|
| 授業の詳細5 |
【 授業計画（後半）】
８．プッシュダウンオートマトン
有限オートマトンにプッシュダウンスタックという特殊な補助記憶装置を付け加えたプッシュダウンオートマトンを理解し，その言語識別能力を学習する。
９・10．チューリング機械
決定性有限オートマトンに作業用の入出力可能な補助テープが与えられたチューリング機械の動作を理解する。また，チューリング機械を「言語の識別機械」ではなく，「計算をする機械」として捉えることができることを具体例から理解する。
11・12．言語の生成装置としての形式文法
形式文法の定義を理解し，どのような形式言語を生成できるかを理解し，形式文法を条件によっていくつかのクラスに分類できることを学習する。
13．正規文法と有限オートマトン
正規文法の定義を理解し，正規文法が生成する言語と有限オートマトンが識別する言語が同じであることを学習する。
14．計算の複雑さ
計算の複雑さに関する基本的な考え方を理解する。
15．最終試験
＊ 言語の生成装置と識別機械の関係を確実に理解できているかどうかを試験によって確認する。
＊ 試験問題は，授業に使用するテキストにある演習問題のレベルとする。
16．『オートマトンと形式言語』で学んだこと
この授業で学んだことを整理する。さらに，返却された最終試験の答案を検討して，各自がこの授業の目標に達しているかどうかを自己点検する。また，まとめとして課される最終課題についてその概要を理解する。
|
| 授業の詳細6 |
【 成績評価 】
成績は，２回の試験結果をもとに評価するが，講義の最後に実施するQuizの結果および最終課題を成績評価の一部に利用する。
◆Ｃ：２回の試験結果の合計が55点以上であることを基準とする。
◆Ｂ：２回の試験結果の合計が65点以上であることを基準とする。
◆Ａ：２回の試験結果の合計が75点以上であることを基準とする。
◆AA：最終課題の完成度を含めて，この授業の目標を完全に達成したと認められた場合
なお，成績評価の詳細は最初の授業で説明する。
□□□□□□□□□□□□□□□□□□□□
◇テキスト
『オートマトン・言語理論の基礎』米田政明・広瀬貞樹・大里延康・大川 和 共著（近代科学社，2003）ISBN 978-4-7649-0297-8
◇参考書
『計算理論とオートマトン言語理論 −コンピュータの原理を明かす−』丸岡 章 著（サイエンス社，2005）ISBN 4-7819-1104-8
◇備 考
履修前提科目＝『情報代数』『離散数学』『情報科学３』
|
| 授業の詳細7 |
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|