オートマトンと言語理論

形式文法で構造が定義されたテキストファイルの解析技術を身に付ける。

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
形式文法が生成する形式言語を示せる。	与えられた文法が生成する終端記号列の集合の階層関係を示せる。	与えられた文法が生成する終端記号列の集合を示せる。	与えられた文法が生成する終端記号列の集合を示せない。
正規表現から最簡形決定性有限オートマトンへ変換できる。	与えられた正規表現が生成する終端記号列の集合を受理する最簡形決定性有限オートマトンを構成できる。	与えられた正規表現が生成する終端記号列の集合を受理する決定性有限オートマトンを構成できる。	与えられた正規表現が生成する終端記号列の集合を受理する決定性有限オートマトンを構成できない。

概要:

形式言語理論とオートマトン理論は形式的に構造が定義されたテキストファイルを解析するための理論的根拠を示している。より具体的には、コンパイラを構成する字句解析器や構文解析器を文法に基づいて実装するために用いられる。

授業の進め方・方法:

授業はスライド資料を用いた講義形式で行う。授業資料は事前に配布する。授業では予習で分らなかったことを中心に理解を深めること。

注意点:

形式言語理論とオートマトン理論は情報工学の基礎となる数学的な理論である。集合の記法を用いて記述されることが多いので事前に慣れておくこと。本講義は、後期の「言語処理系」の準備となる講義である。

アクティブラーニング	ICT 利用	遠隔授業対応	実務経験のある教員による授業

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	概論	プログラム開発環境の構成要素とその役割を示せる。
		2週	概論	コンパイラの構成要素とその役割を示せる。
		3週	文法の記述法	集合論の概略、記号および記号列の集合と演算について示せる。
		4週	文法の記述法	文法を数学的に記述する方法を示せる。
		5週	文法の記述法	文法を生成規則、BNF、拡張BNF、および構文図式で示せる。
		6週	文法の記述法	与えられた文法と終端記号列に対する導出過程と還元過程を示せる。
		7週	演習	ここまでの学習内容に関わる質問に解答できる。
		8週	中間試験	試験において間違えた部分を自分の課題として把握する（非評価項目）。
	2ndQ
		9週	字句解析	有限オートマトンの状態遷移図と受理する言語との関係を示せる。
		10週	字句解析	与えられた正規表現からNFAを作れる。
		11週	字句解析	NFAからDFAを作れる。
		12週	字句解析	DFAから最簡形DFAを作れる。
		13週	字句解析	字句解析器を実際に作るときの配慮事項を示せる。
		14週	演習	ここまでの学習内容に関わる質問に解答できる。
		15週	試験答案の返却・解説	試験において間違えた部分を自分の課題として把握する（非評価項目）。
		16週