科目名 オートマトンと形式言語
単位数 2.0
担当者 情報工学専攻 講師 上土井 陽子(A,B,C,Dクラス担当)
知能工学専攻 教授 松原 行宏(E,F,G,Hクラス担当)
システム工学専攻 教授 中田 明夫(I,J,K,Lクラス担当)
履修時期 前期
履修対象 2年
概要 計算機に代表される情報処理機構の数学的モデルであるオートマトン、並びにプ
ログラミング言語や自然言語の数学的モデルである形式言語を扱う。特に,前者の
中から有限オートマトンおよびプッシュダウンオートマトンを、後者の中から正規
言語および文脈自由言語を取り上げ、それらの関係を明らかにしていく。この講義
を通じ、計算機ソフトウェアおよびハードウェア両分野で必要とされる計算機科学
的な考え方を身につけた学生を育成することを目標とする。
 授業形態:講義
科目の到達目標 有限オートマトンと正規言語、およびプッシュダウンオートマトンと文脈自由言
語について学び、それらの関係を理解する。
受講要件 「離散数学」を十分、理解していることが望ましい。
事前・事後学修の内容 必要に応じて事前事後学修のための課題を課す。
講義内容 1.イントロダクション
2.形式文法と形式言語
3.有限オートマトン
4.正規表現
5.非決定性有限オートマトン
6.正規言語と有限オートマトン
7.正規言語の性質
8.形式文法
9.中間まとめ
10.文脈自由言語の導出木
11.文脈自由文法の性質
12.文脈自由言語の性質
13.プッシュダウンオートマトン
14.文脈自由言語とプッシュダウンオートマトン
15.文脈自由文法,文脈自由言語,プッシュダウンオートマトンに関する総合演習
評価方法 授業の受講状況やレポート課題を勘案し、試験(中間(50%)・期末(50%))の
重みを与え評点を算出し、以下に従って評価を与える.
   秀:評点 90 〜 100点
   優:評点 80 〜 89点
   良:評点 70 〜 79点
   可:評点 60 〜 69点
  不可:評点 59点以下
教科書等 教科書:富田悦治/横森 貴 「オートマトン・言語理論(第2版)」 (森北出版)
参考書:Michael Sipser 著,阿部正幸・植田広樹・藤岡淳・渡辺治 訳 「計算理論の基礎原著第2版 1オートマトンと言語」(共立出版) 
丸岡 章 「計算理論とオートマトン言語理論ーコンピュータの原理を明かす」(サイエンス社)
都倉信樹 「オートマトンと形式言語」(昭晃堂)
 
担当者プロフィール 授業内容や宿題などに関する、学生の個別学習相談を随時受け付けています。
下記問合せ先まで連絡し、各担当教員と個別にアポイントを取って下さい。

上土井陽子 問合せ先:情報科学部棟4階414号室 E-mail:yoko@hiroshima-cu.ac.jp
松原行宏 問合せ先:情報科学部棟6階653号室 E-mail:matsubar@hiroshima-cu.ac.jp
中田明夫 問合せ先:情報科学部棟8階821室 E-mail:nakata@hiroshima-cu.ac.jp
備考 【教職】高一種(数学)