形式言語理論

科目基礎情報

学校 豊田工業高等専門学校 開講年度 平成30年度 (2018年度)
授業科目 形式言語理論
科目番号 95031 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 学修単位: 2
開設学科 情報科学専攻 対象学年 専2
開設期 前期 週時間数 2
教科書/教材 指定しない./教材プリント
担当教員 勝谷 浩明

目的・到達目標

(ア)生成文法が生成する形式言語を理解する.
(イ)文脈自由文法及び文脈自由文法における構文木,最左導出,最右導出について理解する.
(ウ)文脈自由文法の標準形について理解する.
(エ)文脈自由文法の自己埋込み性と正規言語との関係について理解する.
(オ)決定性有限オートマトンと非決定性有限オートマトンとについて認識される言語の範囲が等しいことを理解する.
(カ)正規文法,正規表現,有限オートマトンの各々が規定する言語の範囲が等しいことを理解する
(キ)Turing機械及びプッシュダウンオートマトンの意味と性質とを理解する.
(ク)形式言語の理論がコンパイラの字句解析及び構文解析に応用されることを理解する.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1文脈自由文法・文脈自由言語に関する定理の証明の概要を理解している.文脈自由文法・文脈自由言語に関する定理を理解している.文脈自由文法・文脈自由言語に関する定理を理解していない.
評価項目2正規文法・正規言語・正規表現・有限オートマトンに関する定理の証明の概要を理解している.正規文法・正規言語・正規表現・有限オートマトンに関する定理を理解している.正規文法・正規言語・正規表現・有限オートマトンに関する定理を理解していない.
評価項目3Chomskyの階層に関する定理の証明の概要を理解している.Chomskyの階層に関する定理を理解している.Chomskyの階層に関する定理を理解していない.

学科の到達目標項目との関係

学習・教育到達度目標 A2 ソフトウェア開発において,数理的理論に基づくスマートな設計ができるとともに,ハードウェアの基本動作を意識した設計ができる.
JABEE d 当該分野において必要とされる専門的知識とそれらを応用する能力
本校教育目標 ② 基礎学力

教育方法等

概要:
言語理論の中でも形式言語理論といわれる内容を扱う.形式言語理論は,元々は人間が日常使う自然言語のモデルとして研究が始まったが,その後はプログラミング言語への応用も研究されている.このような事情から,形式言語理論は,情報処理技術において,教養的な意味と,コンパイラの作成などに応用される実用的な意味とを併せ持つ.数学的な議論をする分野であり,きちんと理論を追いかけて理解することが望まれる.
授業の進め方と授業内容・方法:
注意点:
(自学自習内容)配付する教材プリントを読んで予習・復習し,プリントに記載された問題を解くこと.

授業計画

授業内容・方法 週ごとの到達目標
前期
1stQ
1週 数学的準備(集合・写像・数学的帰納法・決定手続き) 集合・写像・数学的帰納法などに関する概念を理解する.
2週 形式言語とその演算(言語の合併,連接,共通部分,Kleene閉包) 形式言語とその演算について理解する.
3週 生成文法(導出,文,生成文法が生成する言語) 生成文法と句構造言語について理解する.
4週 文脈自由言語(構文木,最左導出,最右導出など) 文脈自由文法及び構文木や最左導出について理解する.
5週 文脈自由言語の簡単化(ε規則の除去,有用でない記号の除去など) 文脈自由文法の簡単化について理解する.
6週 文脈自由言語の標準形(Chomskyの標準形,Greibachの標準形) 文脈自由文法の標準形について理解する.
7週 文脈自由文法と正規文法(文脈自由文法の自己埋め込み性) 文脈自由文法と正規文法の関連について理解する.
8週 正規言語と正規表現 正規言語と正規表現について理解する.
2ndQ
9週 決定性有限オートマトンと非決定性有限オートマトン 有限オートマトンとについて理解する.
10週 正規言語と有限オートマトン 正規言語と有限オートマトンとの関係を理解する.
11週 句構造言語の階層 Chomskyの階層について理解する.
12週 Turing機械(Turing機械の拡張,帰納的な言語) Turing機械について理解する.
13週 プッシュダウンオートマトン 文脈自由言語とプッシュダウンオートマトンとの関係を理解する.
14週 字句解析 字句解析の概要を理解する.
15週 構文解析(上向き構文解析,下向き構文解析) 構文解析の概要を理解する.
16週

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週
基礎的能力数学数学数学1次元のデータを整理して、平均・分散・標準偏差を求めることができる。3
2次元のデータを整理して散布図を作成し、相関係数・回帰直線を求めることができる。3

評価割合

定期試験小テスト合計
総合評価割合4060100
専門的能力4060100