タイトル

開講年度 開講学部等
2025 理学部
開講学期 曜日時限 授業形態 AL（アクティブ・ラーニング）ポイント
後期 水1～2 講義 1.0
時間割番号 科目名[英文名] 使用言語 単位数
1042220032 形式言語とオートマトン[Formal Languages and Automaton(Formal Languages and Automata)] 日本語 2
担当教員（責任）[ローマ字表記] メディア授業
上田　仁彦[UEDA Masahiko] ー
担当教員[ローマ字表記]
上田　仁彦　[UEDA Masahiko]
特定科目区分   対象学生   対象年次 2～4
ディプロマ・ポリシーに関わる項目 カリキュラムマップ(授業科目とDPとの対応関係はこちらから閲覧できます)
授業の目的と概要
情報科学の基礎理論のひとつであるオートマトン理論と形式言語理論について学ぶ。また、これらの２つの理論の関係を知る。
授業の到達目標
オートマトン理論が計算機科学の基礎理論となっていることを理解する。また、オートマトンと形式言語の関係を説明できる。
授業計画
【全体】
有限オートマトンの基本動作について説明し、正規文法について解説する。次にこれら２つの関係について言及し、最後に文脈自由文法について解説する。
項目 内容 授業時間外学習 備考
第1回 オートマトンと形式言語 講義で扱う内容について説明する 授業中に指示した内容の復習 (学修時間の目安:４時間以上)
第2回 有限オートマトン(1) 決定性有限オートマトンについて解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第3回 有限オートマトン(2) 決定性有限オートマトンの等価性判定アルゴリズムと最簡形について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第4回 有限オートマトン(3) 非決定性有限オートマトンについて解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第5回 有限オートマトン(4) ε-動作を含む非決定性有限オートマトンについて解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第6回 有限オートマトン(5) 正規表現と正規表現から有限オートマトンへの変換方法について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第7回 有限オートマトン(6) 有限オートマトンから正規表現への変換方法について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第8回 有限オートマトン(7) 正規言語の反復定理と非正規言語について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第9回 形式文法 形式文法、正規文法、正規文法と有限オートマトンの関係について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第10回 文脈自由文法(1) 文脈自由文法、導出木、あいまい性について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第11回 文脈自由文法(2) 文脈自由文法の簡単化について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第12回 文脈自由文法(3) 文脈自由文法の標準形について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第13回 文脈自由文法(4) 文脈自由言語の反復定理について解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第14回 チョムスキー階層 プッシュダウンオートマトン、チューリング機械、句構造文法などについて解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第15回 決定問題 停止問題、計算複雑性などについて解説する 教科書の予習(学修時間の目安: 2時間以上), 授業中に指示した学習内容の復習 (学修時間の目安: 2時間以上)
第16回 まとめ 期末試験 総復習(学修時間の目安:４時間以上)
※AL（アクティブ・ラーニング）欄に関する注
・授業全体で、AL（アクティブ・ラーニング）が占める時間の割合を、それぞれの項目ごとに示しています。
・A〜Dのアルファベットは、以下の学修形態を指しています。
【A：グループワーク】、【B：ディスカッション・ディベート】、【C：フィールドワーク（実験・実習、演習を含む）】、【D：プレゼンテーション】
A: --%　B: --%　C: 10%　D: --%
成績評価法
学期末の筆記テスト(85%)、演習問題(15%)
5回以上の欠席は欠格とする
教科書にかかわる情報
教科書 書名 オートマトン・言語理論 ISBN 9784627805521
著者名 富田悦次, 横森貴共著 出版社 森北出版 出版年 2013
備考
参考書にかかわる情報
参考書 書名 オートマトン 言語理論 計算論 ISBN 9784781910260
著者名 J. ホップクロフト, R. モトワニ, J. ウルマン共著 ; 野崎昭弘 [ほか] 共訳 出版社 サイエンス社 出版年 2003
備考
メッセージ
キーワード
形式言語、オートマトン、形式文法
持続可能な開発目標（SDGs）

  • 産業と技術革新の基盤をつくろう
(インフラ、産業化、イノベーション)強靱（レジリエント）なインフラ構築、包摂的かつ持続可能な産業化の促進及びイノベーションの推進を図る。
関連科目
論理学
履修条件
連絡先
m.ueda@yamaguchi-u.ac.jp
オフィスアワー
木曜13:00-14:00
これ以外の時間にも質問等は随時受け付ける。事前に電子メール等で問い合わせることが望ましい。

ページの先頭へ