| 年度 |
2024年度 |
開講部局 |
情報科学部 |
| 講義コード |
KA107001 |
科目区分 |
専門教育科目 |
| 授業科目名 |
オートマトンと言語理論 |
授業科目名
（フリガナ） |
オートマトントゲンゴリロン |
| 英文授業科目名 |
Theory of Automata and Languages |
| 担当教員名 |
岩本 宙造 |
担当教員名
(フリガナ) |
イワモト チュウゾウ |
| 開講キャンパス |
東広島 |
開設期 |
2年次生 前期 １ターム |
| 曜日・時限・講義室 |
(1T) 火1-2,木5-6：経B255 |
| 授業の方法 |
講義 |
授業の方法
【詳細情報】 |
|
| 講義中心．板書による説明． |
| 単位 |
2.0 |
週時間 |
|
使用言語 |
B
:
日本語・英語 |
| 学習の段階 |
2
:
初級レベル
|
| 学問分野（分野） |
25
:
理工学 |
| 学問分野（分科） |
02
:
情報科学 |
| 対象学生 |
|
| 授業のキーワード |
コンピュータの基礎概念，順序機械，有限オートマトン，形式言語理論 |
| 教職専門科目 |
|
教科専門科目 |
|
プログラムの中での
この授業科目の位置づけ
（学部生対象科目のみ） | |
|---|
到達度評価
の評価項目
（学部生対象科目のみ） | 総合科学プログラム
（知識・理解）
・当該の個別学問体系の重要性と特性、基本となる理論的枠組みへの知識・理解
（能力・技能）
・個別学問体系に関する多様な情報源から必要な文献資料やデータを収集・解析する能力・技能
・課題の考察のために必要な理論・方法を特定する能力・技能
計算機科学プログラム
（知識・理解）
・D1. 計算機科学の基礎となる理論体系を理解し，科学的論理性に基づいた情報処理技術を駆使して，高次元データを収集・処理するための知識と能力．
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術．
・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力．
データ科学プログラム
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術．
・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力．
知能科学プログラム
（知識・理解）
・D1. 人間が持つ高度な知能とその計算機による実現についての体系的な深い理解．
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術．
・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力． |
|---|
| 授業の目標・概要等 |
オートマトンと形式言語理論は，情報科学分野の基盤となる概念である．コ
ンピュータの最も単純な抽象的モデルがオートマトンであり，プログラミング
言語の数学的モデルが形式言語である．また，これらは情報科学における様々
な問題の理論的構造を表現したり，システムを形式化するのに用いられている．
コンピュータの設計・開発を目指すには，背景となっている知識と理論を理
解し活用する必要がある．たとえば，現在のコンピュータの「計算の原理」を
論理的に理解するには「オートマトン理論」の知識が不可欠である．また，実
行させたい計算をコンピュータに提示し，計算手順を指令するには「形式言語
理論」の理解が重要な役割を果たす．本授業では，コンピュータに関する最も
基本的な概念を分かり易く説明する．
１．有限オートマトンの基本的概念を理解する．
２．正規文法と有限オートマトンの関係を学ぶ．
３．文脈自由文法の概念を理解する．
４．オートマトンや形式文法の設計手法を修得する．
|
| 授業計画 |
第1回 ミーリー型とムーア型の順序機械
第2回 有限オートマトン
第3回 等価性判定アルゴリズム
第4回 最簡形，ｋ等価性分類法
第5回 非決定性有限オートマトン，部分集合構成法
第6回 ε動作をもつ非決定性有限オートマトン
第7回 正則集合と正則表現
第8回 有限オートマトンと正則表現の関係
第9回 非正則言語
第10回 正則文法と有限オートマトン
第11回 文脈自由文法
第12回 文脈自由文法の簡単化
第13回 チョムスキー標準形
第14回 グライバッハ標準形，反復補題
第15回 まとめ，試験
|
| 教科書・参考書等 |
講義形式(講義中心)
教科書：「オートマトン・言語理論（第2版・新装版） 」富田悦次・横森貴著 森北出版 ISBN-13: 978-4627805538 |
授業で使用する
メディア・機器等 |
|
| 【詳細情報】 |
|
授業で取り入れる
学習手法 |
|
予習・復習への
アドバイス |
第1回－第15回 各自で取り組むべき課題を授業中に指示する． |
履修上の注意
受講条件等 |
|
| 成績評価の基準等 |
期末試験で評価する．60点以上を合格とする． |
| 実務経験 |
|
実務経験の概要と
それに基づく授業内容 |
|
| メッセージ |
|
| その他 |
|
すべての授業科目において，授業改善アンケートを実施していますので，回答に協力してください。
回答に対しては教員からコメントを入力しており，今後の改善につなげていきます。 |