学期／Semester

2021年度／Academic Yearーター／Third Quarter

3クォ開講期間／Course duration

2021/09/28〜2021/11/24

必修選択／Required / Elective

必修／required

時間割コード／Time schedule code

20213802009501

科目ナンバリングコード／Numbering code

ID‑ID‑2‑095‑1‑101

授業科目名／Course title

オートマトンと言語理論／Automata and Formal Language Theory

曜日・校時／Day・Period

単位数(一般/編入/留学)／Credits(General /Transfer/Overseas)
科目番号／Course code

金／Fri 1, 金／Fri 2

2.0//2.038020095

編集担当教員／Instructor in charge of the酒井 智弥／Sakai Tomoya
course syllabus
授業担当教員名（科目責任者）／Instructor in charge of the course

酒井智弥／Sakai Tomoya

授業担当教員名（オムニバス科目等）／Instructor(s)酒井智弥／Sakai Tomoya

科目分類／Course Category

共通科目, 情報学基盤科目（コンピュータ科学）

対象年次／Intended year

2

教室／Class room

[総合]総合教育研究棟2F多目的ホール, グローバル教育・学生支援課

対象学生（クラス等）

講義形態／Course style

講義／Lecture
文教スカイホール/Intended year (class)

担当教員Eメールアドレス/E‑mail address

tsakai@cis.nagasaki‑u.ac.jp

担当教員研究室/Office

工学部1号館2階情報システム研究室203

担当教員TEL/Tel095‑819‑2583

担当教員オフィスアワー/Office hours

授業の概要及び位置づけ/Course overview

授業到達目標/Course goals

金曜日5校時それ以外は，カレンダー（https://goo.gl/H6Z994）に "NR" と表示している時間帯に研究室に居る予定です．事前に連絡してください（tsakai@cis.nagasaki‑u.ac.jp）．
コンピュータとは何か，コンピュータは何ができて何ができないのか．こういったコンピュータサ
イエンスの本質的な問題について理論的に考えるため，コンピュータおよび計算の対象を数学的に抽象化したオートマトンと形式言語に関する理論を学ぶ．また，この理論が実際の問題にどう応用できるかを理解する．計算量の複雑さを考える基本的概念であり，コンパイラ，ソフトウェア工学を学ぶための基礎に位置づけられる．
計算理論で扱う基本的な計算モデルについて説明でき，モデル間の等価性や計算の可能性を形式的に説明できる．また，これらのモデルを使った簡単な設計ができる．

知識・技能以外に、この授業を通して身につけて欲□主体性／Autonomy ■汎用的能力／Generic Competence □倫理観／Ethics □多様性の理解
しい力（１つ以上３つまで）/Abilities other than／Understanding Diversity □協働性／Cooperativeness □考えをやり取りする力／Ability toknowledge and skills acquired mainly throughexchange ideas □国際・地域社会への関心／Interest in international / local society
the course ( pick 1 to 3 )■A.授業内容の理解度を確認したり自分で考えさせたりする活動 <br>/ Activities to check thedegree of comprehension of the contents to the lesson or to think over
□B.多角的に考えるために他者と関わる活動 <br>/ Activities involving others to think fromvarious perspectives
学生の思考を活性化させるための授業手法/Teaching □C.技能修得のために実践する活動 <br>/ Activities to practice for acquiring skills
method to stimulate students' thinking□D.問題解決のために知識を総合的に活用する活動 <br>/ Activities that comprehensively
utilize knowledge to solve problems□E.上記以外の学生の思考の活性化を促す授業手法 <br>/ Teaching methods to stimulate
students' thinking other than the above□F.教員からの講義のみで構成される <br>/ It consists only of lectures from teachers
定期試験で60点以上の得点があれば合格とする．成績には普段の出席と学習の状況を考慮する．オ
ンラインの定期試験50％，出席レポート50％とした評点を成績とする．ただし，対面の定期試験を成績評価の方法・基準等/Method of evaluation
実施した場合は，定期試験60%，出席レポート40％とした評点と，定期試験100%とした評点の高い方を成績とする．
各回の授業内容・授業方法（学習指導方法）/Course
詳細は授業計画詳細を参照
contents of each lesson
事前、事後学習の内容/Preparation & Review

予習 予め配布された資料および資料に示された教科書の範囲に目を通しながら，オンデマンド教材（講義動画）を視聴すること。また，各回の出席レポートを期日までに提出すること．(2h)
復習 教科書と資料を再読し，各回の出席レポートで理解を確認するように努めること．(2h)キーワード/Keywords

形式言語，形式文法，状態機械，状態遷移表，繰り返し定理，停止問題，計算可能性

教科書・教材・参考書/Materials

教科書：大川 知，広瀬 貞樹，山本 博章「オートマトン・言語理論入門」未来へつなぐデジタルシ
リーズ，共立出版．
教材：印刷した資料を配布する．また，オンデマンド教材（講義の動画）をYouTubeで配信する．
https://youtube.com/playlist?list=PLqcsCBw9njgDaQUdLuSkG8jaL5FpQiUfQ
参考書：ホップクロフト，モトワニ，ウルマン「オートマトン 言語理論 計算論」サイエンス社．
広瀬 貞樹「オートマトン・形式言語理論」コロナ社．
キンバー・スミス「計算論への入門−オートマトン・言語理論・チューリング機械」ピアソン・エデュケーション．

受講要件（履修条件）/Prerequisites

全回出席を前提とする．やむをえず欠席する場合は必ず担当教員に連絡し，指示通り自習とレポートで補うこと．

アクセシビリティ/Accessibility (for studentswith disabilities)

長崎大学では，全ての学生が平等に教育を受ける機会を確保するため，修学の妨げとなり得る社会的障壁の除去及び合理的配慮の提供に取り組んでいます。授業における合理的配慮等のサポートについては，担当教員（上記連絡先参照）または「アシスト広場」（障がい学生支援室）にご相談下
さい。
アシスト広場（障がい学生支援室）連絡先（TEL）095‑819‑2006（FAX）095‑819‑2948（E‑MAIL）support@ml.nagasaki‑u.ac.jp

備考（URL）/Remarks (URL)
学生へのメッセージ/Message for students
実務経験のある教員による授業科目であるか（Y／N)/Instructor(s) with practical experience
実務家教員名／実務経験内容／実務経験に基づく教育内容（実務経験のある教員による授業科目のみ使用）/Name / Details of practical experience /Contents of course
授業計画詳細／Course Schedule

回(日時)／Time(date and time)

授業内容／Contents

第1回

オリエンテーション，数学的準備：

第2回

決定性有限オートマトン(DFA)：

第3回

非決定性有限オートマトン(NFA)：．

第4回

正規表現(RE)・正規言語(RL)：

第5回

正規表現とオートマトンの等価性：

第6回

状態数の最小化：

第7回

非正規言語：

第8回

文脈自由文法(CFG)と構文解析：

第9回

プッシュダウンオートマトン(PDA)：

第10回

文脈自由文法とオートマトンの等価性1：

与えられたCFGをPDAに変換できる．

第11回

文脈自由文法とオートマトンの等価性2：

与えられたPDAをCFGに変換できる．

第12回

非文脈自由言語：

第13回

チューリングマシン(TM)：

第14回

チューリングマシンの計算と言語：

第15回

決定不能性：

第16回

定期試験

計算理論に必要な集合などの形式的記法を理解できる．

DFAの形式的な定義と動作を説明できる．
NFAの形式的な定義を説明でき，NFAを等価なDFAに変換できる

REの形式的な定義を理解し，与えられたREからRLを導出できる．
REからNFA，NFAからREへ変換できる．

オートマトンの状態数を最小化できる．

与えられた言語が正規でないことを証明できる．
CFGから導出される文の構文解析木が書ける．
PDAの形式的な定義と動作を説明できる．

与えられた言語が文脈自由でないことを証明できる．
TMの形式的な定義と動作を説明できる．
万能TMおよびチョムスキー階層を説明できる．

チャーチ・チューリングの提唱と決定不能な問題を説明できる．