2022年度/2B20029001

【火1】オートマトンと形式言語 <前期>

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

担当教員氏名

泉 正夫

科目ナンバリング

授業形態

講義

開講キャンパス

中百舌鳥

開講区分

週間授業

配当年次

カリキュラムにより異なります。

注意: 配当年次は学部・学科によって異なる場合があるので、UNIPAで確認してください。学年指定なしの表記は、要覧等を確認してください。

単位数

2

注意: 実際の単位数は学部・学科によって異なる場合があるので、必ずUNIPAで確認してください。

到達目標

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

各授業回の説明

授業	授業内容	事前・事後の学習内容
第1回	オートマトン・形式言語概論、数学基礎（教科書第１章）	教科書第１章を読んでおくこと
第2回	順序機械，有限オートマトン（教科書第２章第１節，第２節）	教科書2.1節，2.2節を読んでおくこと
第3回	有限オートマトン（教科書第２章第２節）	教科書2.2節を読んでおくこと
第4回	正規言語、等価性（教科書第２章第２節）	教科書2.2節を読んでおくこと
第5回	非決定性有限オートマトン（教科書第２章第３節）	教科書2.3節を読んでおくこと
第6回	言語演算、正規表現（教科書第２章第４節～第７節）	教科書2.4～2.7節を読んでおくこと
第7回	言語と形式文法（教科書第３章）	教科書第３章を読んでおくこと
第8回	文脈自由文法（教科書第４章第１節～第４節）	教科書4.1～4.4節を読んでおくこと
第9回	文脈自由文法の標準形（教科書第４章第５節、第６節）	教科書4.5～4.6節を読んでおくこと
第10回	プッシュダウンオートマトン（教科書第４章第７節～第９節）	教科書4.7～4.9節を読んでおくこと
第11回	非決定性プッシュダウンオートマトン（教科書第４章第１０節～第１３節）	教科書4.10～4.13節を読んでおくこと
第12回	文脈依存文法、句構造文法（教科書第５章）	教科書第５章を読んでおくこと
第13回	線形拘束オートマトン、チューリング機械（教科書第５章）	教科書第５章を読んでおくこと
第14回	決定問題（教科書第６章）	教科書第６章を読んでおくこと
第15回	まとめ	これまでの学習を大まかに復習しておくこと
第16回	定期試験

事前・事後学習の内容

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

成績評価方法

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

履修上の注意

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

教科書

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

Loading...

参考文献

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

オフィスアワー

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

教員への連絡方法（メールアドレス等）

- 外部公開シラバスのためデータがありません / Please use UNIPA syllabus -

その他

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