到達目標
(ア)生成文法が生成する形式言語を理解する．
(イ)文脈自由文法及び文脈自由文法における構文木，最左導出，最右導出について理解する．
(ウ)文脈自由文法の標準形について理解する．
(エ)文脈自由文法の自己埋込み性と正規言語との関係について理解する．
(オ)決定性有限オートマトンと非決定性有限オートマトンとについて認識される言語の範囲が等しいことを理解する．
(カ)正規文法，正規表現，有限オートマトンの各々が規定する言語の範囲が等しいことを理解する．
(キ)Turing機械及びプッシュダウンオートマトンの意味と性質とを理解する．
(ク)形式言語の理論がコンパイラの字句解析及び構文解析に応用されることを理解する．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 文脈自由文法・文脈自由言語に関する定理の証明の概要を理解している． | 文脈自由文法・文脈自由言語に関する定理を理解している． | 文脈自由文法・文脈自由言語に関する定理を理解していない． |
| 評価項目2 | 正規文法・正規言語・正規表現・有限オートマトンに関する定理の証明の概要を理解している． | 正規文法・正規言語・正規表現・有限オートマトンに関する定理を理解している． | 正規文法・正規言語・正規表現・有限オートマトンに関する定理を理解していない． |
| 評価項目3 | Chomskyの階層に関する定理の証明の概要を理解している． | Chomskyの階層に関する定理を理解している． | Chomskyの階層に関する定理を理解していない． |
学科の到達目標項目との関係
学習・教育到達度目標 A2 ソフトウェア開発において，数理的理論に基づくスマートな設計ができるとともに，ハードウェアの基本動作を意識した設計ができる．
JABEE d 当該分野において必要とされる専門的知識とそれらを応用する能力
本校教育目標 ② 基礎学力
教育方法等
概要:
言語理論の中でも形式言語理論といわれる内容を扱う．形式言語理論は，元々は人間が日常使う自然言語のモデルとして研究が始まったが，その後はプログラミング言語への応用も研究されている．このような事情から，形式言語理論は，情報処理技術において，教養的な意味と，コンパイラの作成などに応用される実用的な意味とを併せ持つ．数学的な議論をする分野であり，きちんと理論を追いかけて理解することが望まれる．
授業の進め方・方法:
配付した教材プリントに基づいて講義する．
注意点:
（自学自習内容）配付する教材プリントを読んで予習・復習し，プリントに記載された問題を解くこと．
選択必修の種別・旧カリ科目名
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
数学的準備（集合・写像・数学的帰納法・決定手続き）（課題：数学的帰納法による証明） |
集合・写像・数学的帰納法などに関する概念を理解する．
|
| 2週 |
形式言語とその演算（言語の合併，連接，共通部分，Kleene閉包）（課題：形式言語の演算） |
形式言語とその演算について理解する．
|
| 3週 |
生成文法（導出，文，生成文法が生成する言語）（課題：生成文法が生成する言語の特定） |
生成文法と句構造言語について理解する．
|
| 4週 |
文脈自由言語（構文木，最左導出，最右導出など）（課題：構文木の生成，最左導出の生成） |
文脈自由文法及び構文木や最左導出について理解する．
|
| 5週 |
文脈自由文法の簡単化（ε規則の除去，有用でない記号の除去）（課題：文脈自由文法の簡単化） |
文脈自由文法の簡単化について理解する．
|
| 6週 |
文脈自由言語の標準形（Chomskyの標準形，Greibachの標準形）（課題：Chomskyの標準形への変換） |
文脈自由文法の標準形について理解する．
|
| 7週 |
文脈自由文法と正規文法（文脈自由文法の自己埋め込み性）（課題：文脈自由言語の演算でできる言語を生成する文脈自由文法の構成） |
文脈自由文法と正規文法の関連について理解する．
|
| 8週 |
正規言語と正規表現（課題：正規表現が表す言語の特定） |
正規言語と正規表現について理解する．
|
| 2ndQ |
| 9週 |
決定性有限オートマトンと非決定性有限オートマトン（課題：有限オートマトンが認識する言語の特定） |
有限オートマトンとについて理解する．
|
| 10週 |
正規言語と有限オートマトン（課題：非決定性有限オートマトンが認識する言語を認識する決定性オートマトンの構成） |
正規言語と有限オートマトンとの関係を理解する．
|
| 11週 |
句構造言語の階層（課題：単調文法における導出の試行） |
Chomskyの階層について理解する．
|
| 12週 |
Turing機械（Turing機械の拡張，帰納的な言語）（課題：Turing機械の動きの試行） |
Turing機械について理解する．
|
| 13週 |
プッシュダウンオートマトン（課題：プッシュダウンオートマトンの試行） |
文脈自由言語とプッシュダウンオートマトンとの関係を理解する．
|
| 14週 |
字句解析（課題：有限オートマトンによる字句解析の試行） |
字句解析の概要を理解する．
|
| 15週 |
構文解析（上向き構文解析，下向き構文解析）（課題：構文解析の試行） |
構文解析の概要を理解する．
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 基礎的能力 | 数学 | 数学 | 数学 | 1次元のデータを整理して、平均・分散・標準偏差を求めることができる。 | 3 | |
| 2次元のデータを整理して散布図を作成し、相関係数・回帰直線を求めることができる。 | 3 | |
評価割合
| 定期試験 | 小テスト | 合計 |
| 総合評価割合 | 40 | 60 | 100 |
| 専門的能力 | 40 | 60 | 100 |