山口大学教務システム - 1061530480-言語とオートマトン

開講年度	開講学部等
2022	工学部
開講学期	曜日時限	授業区分	AL（アクティブ・ラーニング）ポイント	YFL育成プログラム
前期	火1～2	講義	0.9
時間割番号	科目名[英文名]			使用言語	単位数
1061530480	言語とオートマトン[Languages and Automata]			日本語	2
担当教員（責任）[ローマ字表記]					メディア授業
伊藤暁[ITOH Akira]					ー
担当教員[ローマ字表記]
伊藤暁　[ITOH Akira]
区分		対象学生		対象年次	3～
ディプロマ・ポリシーに関わる項目			カリキュラムマップ(授業科目とDPとの対応関係はこちらから閲覧できます)

開設科目名（英訳）

Languages and Automata

概要（共通教育の場合は平易な授業案内）

スクリプト言語で利用可能な“正規表現”やコンパイラの作成に欠かせない“文脈自由文法”など，形式言語とオートマトン理論のうちプログラマとして修得しておくべき基礎的概念について系統立てて学習する．

一般目標

（１）言語の概念を理解する．
（２）有限オートマトンの概念を理解する．
（３）非決定性有限オートマトン，ε動作付き有限オートマトンの概念を理解する．
（４）正規表現と有限オートマトンの間の相互変換について理解する．
（５）決定性有限オートマトンの状態数最小化について理解する．
（６）形式文法の諸概念について理解する．

本科目は，知能情報システム工学科の学習・教育目標のうち，以下の項目に該当する：
(D)の(1) 計算，プロセスおよびシステムを理解するための理論を習得する．

授業の到達目標

知識・理解の観点

・言語の諸概念について説明できる．
・有限オートマトンの概念を説明できる．
・非決定性有限オートマトン，ε動作付き有限オートマトンの概念を説明できる．
・正規表現と有限オートマトンの間の相互変換ができる．
・決定性有限オートマトンの状態数を最小化できる．
・形式文法の諸概念を説明できる．

授業計画

【全体】

まず最初に，文字列とその集合である言語に対する種々の演算について学ぶ．引き続き，言語の表現手段として正規表現の概念を学ぶ．次に，有限オートマトンの概念とそれによって受理される言語について学ぶ．これ以後しばらくの間，正規表現と有限オートマトンが互いに変換可能であることを学ぶ．その際，中間媒介として決定性有限オートマトンを拡張した非決定性有限オートマトン，ε動作付き有限オートマトンが導入される．また，決定性有限オートマトンの状態数を最小化するためのアルゴリズムを学ぶ．
　以上によって，２つの異なる正規表現が同一の言語を表現しているかどうかの判定，あるいは与えられた正規表現が表現する言語の補集合を表現する正規表現を求めることが出来るようになる．
　最後に，形式文法の諸概念について学ぶ

	項目	内容	授業外指示	授業記録	※
	項目	内容	授業外指示	授業記録	A	B	C	D	E	F
第1回	言語	再帰的定義，順列生成アルゴリズム	再帰的定義に慣れる．空列と空集合を区別する．捕集合言語を強く意識する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第2回	正規表現	00を含まない文字列，1が一つ以上含まれるならば最後が00の文字列	正規表現が表現する言語を日本語で正確に記述する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第3回	状態遷移図	10進2進変換、切り下げ関数、自然数の加算	状態遷移図の有用性を確認する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第4回	有限オートマトン	初期状態，受理状態，死状態，状態遷移関数，受理言語	まず実現可能性を無視する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第5回	非決定性有限オートマトン	非決定性の解消，部分集合構成法	まず実現可能性を無視する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第6回	ε動作付き非決定性有限オートマトン	ε動作の解消，ε-closure	まず実現可能性を無視する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第7回	部分集合構成法	決定性オートマトンへの変換	ε動作付きから決定性への（ε動作無しを経ない）変換方法に慣れる．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第8回	状態方程式	出力系，入力系	定数項εの使い方を間違えない．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第9回	有限オートマトンから正規表現への変換	自己ループの解消と状態の削除	遷移図の変形と式変形を同時に追跡する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第10回	正規表現から有限オートマトンへの変換	正規表現の各演算に対応するオートマトンの合成法	最終的に線形代数の初等的内容と同一であったと認識する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第11回	有限オートマトンの状態数最小化	状態間の同値関係，深さ優先探索	出力系との対応を意識する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第12回	正規言語の閉包性と決定問題	閉包性：ブール演算など．決定問題：等価性判定など	正規表現の補表現を求めることが出来る．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第13回	正規文法	右線形文法，左線形文法，導出，導出木	状態方程式が正規文法そのものであることを認識する．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第14回	文脈自由文法	文脈自由と文脈依存，曖昧性	構文だけでなく意味も考慮した文法に書き換える．		-----	-----	【少】（授業時間の15％未満）	-----	-----	-----


第15回	期末試験				-----	-----	-----	-----	-----	-----

※AL（アクティブ・ラーニング）欄に関する注　
①A〜Fのアルファベットは、以下の学修形態を指しています。
【A：グループワーク】、【B：ディスカッション・ディベート】、【C：フィールドワーク（実験・実習、演習を含む）】、【D：プレゼンテーション】
【E：振り返り】、【F：宿題】
②【多】、【中】、【少】は授業時間内におけるALが占める時間の割合を指しています。
【多】：授業時間の50％超、【中】：授業時間の15％〜50％、【少】：授業時間の15％未満。「振り返り」と「宿題」については該当する場合に【あり】と表示されます。

成績評価法

【全体】

小テスト5%，レポート5%, 期末試験90%で評価する．

【観点別】

	知識・理解	思考・判断	関心・意欲	態度	技能・表現	その他	評価割合（％）	JABEE収集資料
定期試験（中間・期末試験）	◎	---	---	---	---	---	90%	---
小テスト・授業内レポート	○	○	○	---	---	---	---	---
宿題・授業外レポート	○	○	○	---	---	---	---	---
授業態度・授業への参加度	---	---	---	---	---	---	評価に加えず	---
受講者の発表（プレゼン）・授業内での制作作品	---	---	---	---	---	---	評価に加えず	---
演習	---	---	---	---	---	---	評価に加えず	---
出席	---	---	---	---	---	---	欠格条件	---
その他	---	---	---	---	---	---	評価に加えず	---

教科書にかかわる情報

教科書	書名	オートマトン言語理論計算論				ISBN	4781910262
教科書	著者名	J. ホップクロフト, R. モトワニ, J. ウルマン	出版社	サイエンス社				出版年	2003

備考

補助教材としてプリントを配布する．

参考書にかかわる情報

参考書	書名	オートマトン・言語理論（第２版）				ISBN	4627805527
参考書	著者名	富田 , 横森	出版社	森北出版				出版年	2013

参考書	書名	計算理論の基礎				ISBN	4320029488
参考書	著者名	Michael Sipser	出版社	共立出版				出版年	2000

備考

メッセージ

プログラミングとは本来文字列を扱う作業である．本授業では正規表現や文脈自由文法など，直接役立つ概念の修得を最優先するが，それらを突き詰めるとある種の数学になることに気づいて欲しい．

キーワード

形式言語，正規表現，有限オートマトン，文脈自由文法

持続可能な開発目標（SDGs）

(インフラ、産業化、イノベーション)強靱（レジリエント）なインフラ構築、包摂的かつ持続可能な産業化の促進及びイノベーションの推進を図る。

メディア授業