開講年度
開講学部等
2025
工学部
開講学期
曜日時限
授業形態
AL（アクティブ・ラーニング）ポイント
前期
金3～4
1.0
時間割番号
科目名[英文名]
使用言語
単位数
1061530750
オートマトンと言語処理系[Automata and Compiler]
日本語
2
担当教員（責任）[ローマ字表記]
メディア授業
荒木 徹也[ARAKI Tetsuya]
ー
担当教員[ローマ字表記]
荒木 徹也 [ARAKI Tetsuya]
特定科目区分
対象学生
対象年次
3～
ディプロマ・ポリシーに関わる項目
カリキュラムマップ(授業科目とDPとの対応関係はこちらから閲覧できます)
メディア授業
×
メディア授業とは，メディアを利用して遠隔方式により実施する授業の授業時数が，総授業時数の半数を超える授業をいいます。
メディア授業により取得した単位は，卒業要件として修得すべき単位のうち60単位を超えないものとされています。
授業の目的と概要
ソフトウエア工学の基礎になるオートマトン理論のうちプログラマとして修得しておくべき基礎的な概念について系統立てて学習する．また，プログラム変換に必要なコンパイラの一般的な処理の流れやコンパイラを構成するアルゴリズムなどを講述する．
授業の到達目標
・コンパイラの処理の流れを説明できる．
・言語の概念について説明できる．
・有限オートマトンの概念を説明できる．
・正規表現と有限オートマトンの間の相互変換ができる．
・文脈自由文法の諸概念を説明できる．
授業計画
【全体】
最初に，コンパイラの一般的な処理の流れと文字列とその集合である言語に対する種々の演算について学ぶ．
次に，有限オートマトンの概念と正規表現と有限オートマトンが互いに変換できることを学ぶ．
最後に，文脈自由文法の諸概念について学び，オートマトンと形式文法の関係性について学ぶ．
項目
内容
授業時間外学習
備考
第1回
オートマトンとコンパイラ
オートマトンの概要とコンパイラの処理の流れ
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第2回
有限オートマトン1
有限オートマトンの定義
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第3回
有限オートマトン2
状態遷移図と状態遷移表
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第4回
非決定性有限オートマトン
非決定性有限オートマトンの定義
非決定性有限オートマトンから決定性有限オートマトンへの変換
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第5回
オートマトンの等価性
等価な有限オートマトンの定義等
有限オートマトンの等価性判定
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第6回
正規表現
正規表現の定義
正規表現から有限オートマトンへの変換
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第7回
プッシュダウンオートマトン
プッシュダウンオートマトンの定義
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第8回
中間試験
中間試験
演習問題の見直しを中心に４時間以上学習すること
第9回
チューリング機械
チューリング機械の定義
チューリング機械の状態遷移
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第10回
形式文法
形式文法の定義
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第11回
正規文法
正規文法の定義
正規文法から有限オートマトンへの変換
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第12回
文脈自由文法１
文脈自由文法の定義
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第13回
文脈自由文法２
文脈自由文法の簡略化
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第14回
文脈自由文法の標準形
チョムスキー標準形
グライバッハ標準形
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第15回
オートマトンと形式文法
文脈自由文法から非決定性プッシュダウンオートマトンへの変換
授業中に指示した内容の復習
(学修時間の目安:４時間以上)
第16回
期末試験
期末試験
後半の演習問題の見直しを中心に４時間以上学習すること
※AL（アクティブ・ラーニング）欄に関する注
・授業全体で、AL（アクティブ・ラーニング）が占める時間の割合を、それぞれの項目ごとに示しています。
・A〜Dのアルファベットは、以下の学修形態を指しています。
【A：グループワーク】、【B：ディスカッション・ディベート】、【C：フィールドワーク（実験・実習、演習を含む）】、【D：プレゼンテーション】
A: --% B: --% C: 10% D: --%
成績評価法
出席は欠格条件とし，４回以上の欠席は欠格とします．
中間試験50%，期末試験50%
教科書にかかわる情報
備考
授業に関する資料を随時配布する．
参考書にかかわる情報
参考書
書名
はじめて学ぶオートマトンと言語理論
ISBN
9784627852914
著者名
藤原暁宏著
出版社
森北出版
出版年
2015
参考書
書名
計算理論とオートマトン言語理論 : コンピュータの原理を明かす
ISBN
9784781915210
著者名
丸岡章著
出版社
サイエンス社
出版年
2021
備考
メッセージ
キーワード
正規表現，有限オートマトン，文脈自由文法
持続可能な開発目標（SDGs）
(教育)すべての人に包摂的かつ公正な質の高い教育を確保し、生涯学習の機会を促進する。
(インフラ、産業化、イノベーション)強靱（レジリエント）なインフラ構築、包摂的かつ持続可能な産業化の促進及びイノベーションの推進を図る。
関連科目
履修条件
連絡先
E-mail: tetsuya.araki[at]yamaguchi-u.ac.jp
※[at]の部分を@に書き換えてメールしてください．
オフィスアワー
電子メールで随時受け付けます．
ページの先頭へ