オートマトンと形式言語

科目名
Course Title
授業コード 単位数 配当年次 開講期間
Term
科目分類 ナンバリング
コード
曜日
コマ
教室 担当教員氏名
Instructor
オートマトンと形式言語
B100140001 2 3 前期授業 専門科目 AKPRI2207-J1 火1 B3-118 泉 正夫

オフィスアワー

月曜1コマ(9:00~10:30)B3棟502室

授業目標

計算機科学における最も重要な基礎的分野である言語とその処理機構ならびに計算のアルゴリズムの定式化に関する理解を得ることを目指す。講義では、オートマトンと言語の基本概念、有限オートマトンと正規表現について説明する。次いで、形式文法ならびに文脈自由文法とプッシュダウンオートマトンについて講述し、言語処理の概念を把握する。さらに、計算の一般的モデルであるチューリング機械と句構造文法について説明する。具体的には、以下の基本的事項を目標とする。
1.有限オートマトンと正規文法について、その基本概念と動作原理を理解する。
2.プッシュダウンオートマトンと文脈自由文法の基本概念と動作原理を理解する。
3.線形拘束オートマトン、チューリング機械と文脈依存文法、句構造文法の基本概念を理解する。

教科書

富田悦次、横森貴「オートマトン・言語理論(第2版)」森北出版

参考書

ホップクロフト,ウルマン著、野崎昭弘,木村泉訳「言語理論とオートマトン」(サイエンス社)

関連科目

データ構造とアルゴリズム、計算機アーキテクチャ、コンピュータアーキテクチャ 他

授業時間外の学習(準備学習等について)

授業時間だけでは、この講義の内容を理解し、その理解を定着させることはできない。授業の復習は勿論のこと、予習も必要である。「授業計画」欄にいつ教科書のどの節を講義するかが示されているので、授業前にその節の内容を必ず読み、分からない箇所を明確にしておくこと。(予習では全部分かる必要はない)また、復習のサポートとして、講義で用いたスライドをPDFファイルにして、講義後「授業支援システム」に掲載するので、各自活用してください。

授業の概要

以下の項目を講義する。
・オートマトンと形式言語の基本概念
・有限オートマトンと正規文法
・プッシュダウンオートマトンと文脈自由文法
・線形拘束オートマトン、チューリング機械の基本概念
・文脈依存文法、句構造文法の基本概念

授業計画

第1回 オートマトン・形式言語概論、数学基礎(教科書第1章) 準備学習等 教科書第1章を読んでおくこと
第2回 順序機械,有限オートマトン(教科書第2章第1節,第2節) 準備学習等 教科書2.1節,2.2節を読んでおくこと
第3回 有限オートマトン,正規言語、等価性(教科書第2章第2節) 準備学習等 教科書2.2節を読んでおくこと
第4回 非決定性有限オートマトン(教科書第2章第3節) 準備学習等 教科書2.3節を読んでおくこと
第5回 言語演算、正規表現(教科書第2章第4節~第7節) 準備学習等 教科書2.4~2.7節を読んでおくこと
第6回 言語と形式文法(教科書第3章) 準備学習等 教科書第3章を読んでおくこと
第7回 文脈自由文法(教科書第4章第1節~第4節) 準備学習等 教科書4.1~4.4節を読んでおくこと
第8回 文脈自由文法の標準形(教科書第4章第5節、第6節) 準備学習等 教科書4.5~4.6節を読んでおくこと
第9回 プッシュダウンオートマトン(教科書第4章第7節~第9節) 準備学習等 教科書4.7~4.9節を読んでおくこと
第10回 非決定性プッシュダウンオートマトン(教科書第4章第10節~第13節) 準備学習等 教科書4.10~4.13節を読んでおくこと
第11回 文脈依存文法、句構造文法(教科書第5章) 準備学習等 教科書第5章を読んでおくこと
第12回 線形拘束オートマトン、チューリング機械(教科書第5章) 準備学習等 教科書第5章を読んでおくこと

成績評価

小テストの合計2割+定期試験8割で評価する。合計評価100点満点中6割以上(60点以上)取得者を合格とする。
ただし、定期試験を受験するには小テストを全回数の8割以上提出していることが必要。
定期試験では講義内容、特に「授業概要」に示されている5つの項目を理解できているかどうかを評価する。

備考(実務経験の活用を含む)

小テストは毎回行います.授業支援システムへ提出するよう指示された場合は,示された期限内に提出してください.