【授業の目的】
形式文法，形式言語，オートマトンについて学ぶ．
形式文法，形式言語といった概念を習得する．さらに，オートマトンとの関係について学ぶ．
【授業の到達目標】
・形式言語および形式文法の概念を修得する．
・有限オートマトンおよびプッシュダウンオートマトンについて理解する．
・構文解析アルゴリズムを理解する．
・形式言語の各種クラスとその性質を理解する．
【授業概要（キーワード）】
形式言語，形式文法，文脈自由言語，プッシュダウンオートマトン，構文解析
【科目の位置付け】
本授業はシステム情報学コース専門教育科目（専門科目）に該当し，形式言語とオートマトンについて学ぶものである（地域教育文化学部のカリキュラムポリシー 4）．
【授業計画】
・授業の方法
適宜演習を交えながら講義を行う．
・日程
第１回：形式言語とは
第２回：有限オートマトン
第３回：非決定性有限オートマトン
第４回：正規表現
第５回：有限オートマトンと正規表現の関係
第６回：正規言語の性質および正規言語の繰り返し補題
第７回：有限オートマトンの状態数最小化
第８回：形式文法とそのクラス
第９回：導出，空語問題，空問題
第１０回：チョムスキー標準形
第１１回：文脈自由言語の繰り返し補題
第１２回：プッシュダウンオートマトン
第１３回：最終状態受理と空スタック受理の等価性
第１４回：構文解析
第１５回：まとめと総合演習，試験
【学習の方法】
・受講のあり方
各トピックの習得にはそれ以前のトピックを理解していることが不可欠である．疑問が生じた際にはできるだけ早く解決するように努めること．
・授業時間外学習へのアドバイス
予習が必要な際はあらかじめ授業資料をWeb上に公開するので目を通しておくこと．
授業中に解いた演習問題を中心に，単に「解き方」だけでなく「内容の理解」に努めること．
【成績の評価】
・基準
形式言語および形式文法の概念を正しく理解しているか．
有限オートマトンやプッシュダウンオートマトンについて，構成法を含め様々な性質を正しく理解しているか．
各種形式言語のクラスについて，その特徴やオートマトンとの関係を正しく理解しているか．
基本的な構文解析アルゴリズムを理解しているか．
・方法
試験により評価する．
【テキスト・参考書】
授業中に資料を配布する．
参考書：都倉信樹 著「オートマトンと形式言語」昭晃堂
参考書：守屋悦朗 著「形式言語とオートマトン」サイエンス社
【その他】
・オフィス・アワー
質問は随時受け付けるが，あらかじめ連絡をすることが望ましい．
|