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