科目名	オートマトンと形式言語
単位数	2.0
担当者	知能工学専攻　教授　松原 行宏
履修時期	前期（第2ターム）
履修対象	2年
講義形態	講義
講義の目的	計算機に代表される情報処理機構の数学的モデルであるオートマトン，並びにプログラミング言語や自然言語の数学的モデルである形式言語を学ぶ．特に，前者の中から有限オートマトンおよびプッシュダウンオートマトンを，後者の中から正規言語および文脈自由言語を学び，それらの関係を理解する．この講義を通じ，計算機ソフトウェアおよびハードウェア両分野で必要とされる計算機科学的な考え方を身につける．
到達目標	・有限オートマトンと正規言語について説明できる．　【知識２、技能１】 ・プッシュダウンオートマトンと文脈自由言語について説明できる．　【知識２、技能１】
受講要件	「離散数学」を十分，理解していることが望ましい．
履修取消の可否	否
履修取消不可の理由	・必修科目であるため．
事前・事後学修	・事前にWebClass等を通じて提示する配布資料を読み，自分の考えをまとめる． ・授業で取り組んだテーマに関する提出課題を完成させる．
講義内容	１．イントロダクション ２．形式文法と形式言語 ３．有限オートマトン ４．正規表現 ５．非決定性有限オートマトン ６．正規言語と有限オートマトン ７．正規言語の性質 ８．形式文法 ９．中間まとめ １０．文脈自由言語の導出木 １１．文脈自由文法の性質 １２．文脈自由言語の性質 １３．プッシュダウンオートマトン １４．文脈自由言語とプッシュダウンオートマトン １５．文脈自由文法，文脈自由言語，プッシュダウンオートマトンに関する総合演習 ※授業の順序は変更することがある． ※上記とは別に期末試験を実施する．
期末試験実施の有無	実施する
評価方法・基準	授業の受講状況やレポート課題を勘案し，試験（中間（５０％）・期末（５０％））の重みを与え，有限オートマトンと正規言語ならびにプッシュダウンオートマトンと文脈自由言語を理解しているか評点を算出し，以下に従って評価を与える． 　　　秀：評点 90 -100点 　　　優：評点 80 - 89点 　　　良：評点 70 - 79点 　　　可：評点 60 - 69点 　　不可：評点 59点以下
教科書等	教科書：富田悦治／横森　貴　「オートマトン・言語理論（第２版）」　（森北出版） 参考書：Michael Sipser 著，阿部正幸・植田広樹・藤岡淳・渡辺治 訳　「計算理論の基礎原著第２版　１オートマトンと言語」（共立出版）　 丸岡　章　「計算理論とオートマトン言語理論ーコンピュータの原理を明かす」（サイエンス社） 都倉信樹　「オートマトンと形式言語」（昭晃堂）
担当者プロフィール	授業内容や宿題などに関する，学生の個別学習相談を随時受け付けています． 下記問合せ先まで連絡し，担当教員とアポイントを取って下さい． 松原行宏 問合せ先：情報科学部棟6階653号室 E-mail:matsubar@hiroshima-cu.ac.jp
講義に関連する実務経験
課題や試験に対するフィードバック	・小テストや提出課題については，模範解答を説明する． ・試験後に模範解答を示す． ・提出したレポートは後日講評する．
アクティブ・ラーニング	プレゼンテーション
キーワード	有限オートマトン，正規言語，プッシュダウンオートマトン，文脈自由言語
備考	【教職】高一種（数学）