岡山県立大学：シラバス

授業科目名（和文）［Course］	形式言語理論
授業科目名（英文）［Course］	Formal Language Theory
学部（研究科）［Faculty］	情報系工学研究科
学科（専攻）［Department］	システム工学専攻前期
担当教員（○：代表教員） [Principle Instructor(○) and Instructors]	○國島　丈生　　自室番号（2610）、電子メール（kunishic.oka-pu.ac.jp） ※利用の際は, を @に置き換えてください
単位数［Point(Credit)］	前期 2単位
対象学生［Eligible students］	1・2年次生
授業概略と目標［Course description and Objects］	言語理論とオートマトン理論のうち、有限オートマトンと正則表現、文脈自由文法、プッシュダウンオートマトンなど、情報科学の理論・応用の両面で重要になっている項目について学び、理解を深めます。
到達目標［Learning Goal］	1. 有限オートマトンの主要な性質、応用などについて理解する。 2. 正則表現の主要な性質、応用などについて理解する。 3. 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用などについて理解する。
履修上の注意［Notes］	履修の要件:集合、数学的帰納法など、情報数学の基本事項について理解していること。
授業計画とスケジュール［Course schedule］	1. 導入・本講義で扱う内容について、応用面も含めて俯瞰的な説明を行う。 2. 言語理論の基礎概念・本講義を通して用いる言語理論の基礎的な概念について説明する。 3. 決定性有限オートマトン(DFA) ・DFAの概要、定義、動作などについて、例を用いながら説明する。 4. 非決定性有限オートマトン(NFA)とDFA ・NFAの定義や動作についてDFAと対比させながら説明し、DFAとNFAの等価性を示す。 5. 正則表現・正則表現（正規表現）について、言語理論の視点から説明する。 6. 有限オートマトンと正則表現の応用・有限オートマトンや正則表現が実際にどのように活用されているのか、例を交えて説明する。 7. 正則表現と有限オートマトンの等価性・正則表現と有限オートマトンの等価性について、証明の概要を交えて説明する。 8. 正則言語とその性質・ポンプの補題、正則言語の閉包性などについて説明する。 9. 有限オートマトンの状態数最小化・有限オートマトンの状態数最小化アルゴリズムについて説明する。 10. 文脈自由文法(CFG) ・CFGの定義や意味について、例を用いながら説明する。 11. 構文木とCFG ・文脈自由文法と関わりの深いデータ構造である構文木について、CFGとの関連を交えて説明する。 12. 文脈自由文法の応用・CFGが実際にどのように活用されているのか、例を交えて説明する。 13. プッシュダウンオートマトン(PDA) ・PDAの概要、定義、動作などについて説明する。 14. CFGとPDAの等価性・CFGとPDAの等価性について、証明の概要を交えて説明する。 15. 文脈自由言語とその性質・CFGに関する諸性質について説明する。
成績評価方法と基準［Grading policy (Evaluation)］	定期試験（もしくはそれに相当するレポート課題）80%、学習態度20%によって総合的に判定する。
教科書［Textbook］	教科書: 「オートマトン言語理論計算論I (第2版)」, J. ホップクロフトほか, サイエンス社参考書: 使用しない
自主学習ガイド及びキーワード［Self learning］	講義時間の制約上、証明の詳細は省略することが多いが、言語理論を深く理解するには教科書に掲載されている証明も時間をかけて読んでみることが望ましい。キーワード：有限オートマトン、正則表現（正規表現）、文脈自由文法、プッシュダウンオートマトン
開講年度［Year of the course］	28

授業科目名（和文）［Course］	形式言語理論
授業科目名（英文）［Course］	Formal Language Theory
学部（研究科）［Faculty］	情報系工学研究科
学科（専攻）［Department］	システム工学専攻前期
担当教員（○：代表教員） [Principle Instructor(○) and Instructors]	○國島　丈生　　自室番号（2610）、電子メール（kunishic.oka-pu.ac.jp） ※利用の際は, を @に置き換えてください
単位数［Point(Credit)］	前期 2単位
対象学生［Eligible students］	1・2年次生
授業概略と目標［Course description and Objects］	言語理論とオートマトン理論のうち、有限オートマトンと正則表現、文脈自由文法、プッシュダウンオートマトンなど、情報科学の理論・応用の両面で重要になっている項目について学び、理解を深めます。
到達目標［Learning Goal］	1. 有限オートマトンの主要な性質、応用などについて理解する。 2. 正則表現の主要な性質、応用などについて理解する。 3. 文脈自由文法とプッシュダウンオートマトンの主要な性質、応用などについて理解する。
履修上の注意［Notes］	履修の要件:集合、数学的帰納法など、情報数学の基本事項について理解していること。
授業計画とスケジュール［Course schedule］	1. 導入・本講義で扱う内容について、応用面も含めて俯瞰的な説明を行う。 2. 言語理論の基礎概念・本講義を通して用いる言語理論の基礎的な概念について説明する。 3. 決定性有限オートマトン(DFA) ・DFAの概要、定義、動作などについて、例を用いながら説明する。 4. 非決定性有限オートマトン(NFA)とDFA ・NFAの定義や動作についてDFAと対比させながら説明し、DFAとNFAの等価性を示す。 5. 正則表現・正則表現（正規表現）について、言語理論の視点から説明する。 6. 有限オートマトンと正則表現の応用・有限オートマトンや正則表現が実際にどのように活用されているのか、例を交えて説明する。 7. 正則表現と有限オートマトンの等価性・正則表現と有限オートマトンの等価性について、証明の概要を交えて説明する。 8. 正則言語とその性質・ポンプの補題、正則言語の閉包性などについて説明する。 9. 有限オートマトンの状態数最小化・有限オートマトンの状態数最小化アルゴリズムについて説明する。 10. 文脈自由文法(CFG) ・CFGの定義や意味について、例を用いながら説明する。 11. 構文木とCFG ・文脈自由文法と関わりの深いデータ構造である構文木について、CFGとの関連を交えて説明する。 12. 文脈自由文法の応用・CFGが実際にどのように活用されているのか、例を交えて説明する。 13. プッシュダウンオートマトン(PDA) ・PDAの概要、定義、動作などについて説明する。 14. CFGとPDAの等価性・CFGとPDAの等価性について、証明の概要を交えて説明する。 15. 文脈自由言語とその性質・CFGに関する諸性質について説明する。
成績評価方法と基準［Grading policy (Evaluation)］	定期試験（もしくはそれに相当するレポート課題）80%、学習態度20%によって総合的に判定する。
教科書［Textbook］	教科書: 「オートマトン言語理論計算論I (第2版)」, J. ホップクロフトほか, サイエンス社参考書: 使用しない
自主学習ガイド及びキーワード［Self learning］	講義時間の制約上、証明の詳細は省略することが多いが、言語理論を深く理解するには教科書に掲載されている証明も時間をかけて読んでみることが望ましい。キーワード：有限オートマトン、正則表現（正規表現）、文脈自由文法、プッシュダウンオートマトン
開講年度［Year of the course］	28