文理学部シラバスTOP > 文理学部 > 情報科学科（情報システム解析学科） > オートマトンと形式言語
日本大学ロゴ

オートマトンと形式言語

このページを印刷する

令和元年度以前入学者 オートマトンと形式言語
平成28年度以前入学者 応用形式言語
教員名 斎藤明
単位数    2 学年    3 開講区分 文理学部
科目群 情報科学科
学期 前期 履修区分 選択必修
授業の形態 オンデマンド型の遠隔授業（15回）
授業概要 前半は有限オートマトン，正則表現，正則文法の等価性およびそれらの応用を解説する．後半は，文脈自由文法を中心に，言語の形式的な表現方法と構文解析法を解説する．授業時間に余裕があるときには，文脈自由文法の標準形，文脈自由文法とプッシュダウンオートマトンの等価性，言語に関するチョムスキー階層などについても解説する．
授業のねらい・到達目標 状態遷移の操作的な定義方法と言語の形式的な表現方法が理解できるようになる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法 講義を中心に行うが、必要に応じて授業内演習で理解を深める。
履修条件 2年次科目の「離散数学」と「グラフ理論」を履修していること．
授業計画
1 これまでの講義で学んだ内容のうち、本講義で使用するものを復習する。
【事前学習】集合，関係，写像について復習する。 （2時間）
【事後学習】記号列と言語に関する各種概念を復習する。 （2時間）
2 決定性有限オートマトンとその受理言語の概念を学ぶ。
【事前学習】記号列に関する各種概念を復習する。 （2時間）
【事後学習】決定性有限オートマトンとその受理言語に関して授業中に出題される問題を解く。 （2時間）
3 非決定性有限オートマトンとその受理言語の概念を学ぶ。
【事前学習】決定性有限オートマトンとその受理言語に関して復習する。 （2時間）
【事後学習】決定性有限オートマトンとその受理言語に関して授業中に出題される問題を解く。 （2時間）
4 空動作を許す非決定性有限オートマトンとその受理言語の概念を学ぶ。
【事前学習】空動作のある決定性有限オートマトンとその受理言語に関して復習する。 （2時間）
【事後学習】空動作のある決定性有限オートマトンとその受理言語に関して授業中に出題される問題を解く。 （2時間）
5 正規表現の概念と、与えられた正規表現を受理する有限オートマトンの構成法を学ぶ。
【事前学習】空動作のある決定性有限オートマトンとその受理言語について復習する。 （2時間）
【事後学習】講義で提示される正規表現について、それを受理する決定性オートマトンを構成する問題を解く。 （2時間）
6 有限オートマトンの最小化について学ぶ。
【事前学習】同値関係について復習する。 （2時間）
【事後学習】オートマトンの最小化について講義中に出題される問題を解く。 （2時間）
7 有限オートマトンと正規表現に関するまとめと補足を行う。
【事前学習】オートマトンの最小化に関して復習する。 （2時間）
【事後学習】講義中に出題される正規表現とオートマトンの総合問題を解く。 （2時間）
8 有限オートマトンと正規表現に関する応用例題を解説する。
【事前学習】これまでに講義で出題された問題を解き直す。 （2時間）
【事後学習】授業中に出題された例題を解き直す。 （2時間）
9 ポンプの補題を学び、正規表現の限界を知る。
【事前学習】教科書P.41にある問（正規表現を受理する決定性有限オートマトンの構成）を解く。 （2時間）
【事後学習】ポンプの補題を用いて、講義で出題される表現が正規表現ではないことを示す。 （2時間）
10 形式文法の概念を学ぶ。
【事前学習】ポンプの補題を復習する。 （2時間）
【事後学習】講義で与えられた文法の導出を求める。 （2時間）
11 正規文法と正規言語の概念を学ぶ。
【事前学習】形式文法の概念を復習する。 （2時間）
【事後学習】講義で与えられた有限オートマトンが受理する言語の文法を求める。 （2時間）
12 プッシュダウンオートマトンの概念を学ぶ。
【事前学習】正規言語と有限オートマトンの関係を復習する。 （2時間）
【事後学習】決定性・非決定性プッシュダウンオートマトンの動作を理解する。 （2時間）
13 文脈自由文法の概念を学ぶ。
【事前学習】プッシュダウンオートマトンとそれが受理する言語について復習する。 （2時間）
【事後学習】講義で与えられた文脈自由言語について、それを受理するプッシュダウンオートマトンを構成する。 （2時間）
14 構文解析について学ぶ。
【事前学習】教科書94～99ページに書かれた構文解析の説明を予習し、不明な点をまとめておく。 （2時間）
【事後学習】下降型、上昇型という2つの構文解析について、理解を深める。 （2時間）
15 チューリングマシンの概念を学ぶ。
【事前学習】教科書119～129ページに書かれたチューリングマシンの説明を意味、不明な点をまとめておく。 （2時間）
【事後学習】講義で提示されたチューリングマシンが受理する言語を求める。 （2時間）
その他
教科書 岡留剛 『例解図説 オートマトンと形式言語入門』 森北出版 2015年 第1版
参考書 使用しない
成績評価の方法及び基準 試験(70%)、授業参画度:毎回課す宿題の提出状況と内容(30%)
試験は15回の講義が全て終了した後に、オンラインで試験を行う。その結果と宿題の提出状況・内容を元に評価する。
オフィスアワー 毎週火曜日の 12:10～13:00 をオンライン上でのオフィスアワーとする。具体的な方法は BlackBoard にて指示する。可能であれば電子メールにてアポイントを取ること。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合には、そちらを優先する。

↑このページのトップ