| 理想的な到達レベルの目安(優/良) | 標準的な到達レベルの目安(可) | 未到達レベルの目安 |
評価項目1(B1-4) | □形式言語と形式言語に関わる基本的な定義や概念について他人に説明できる | | □形式言語と形式言語に関わる基本的な定義や概念について他人に説明できない |
評価項目2 | □可の基準に加えて正規言語で表現できない言語が存在することをポンプの補題で証明できる | □正規文法やオートマトンによって正規言語を正しく定義できる | □正規文法やオートマトンによって正規言語を正しく定義できない |
評価項目3 | □可の基準に加えて文脈自由言語で表現できない言語が存在することをポンプの補題で証明できる | □文脈自由文法やプッシュダウン・オートマトンによって文脈自由言語を正しく定義できる | □文脈自由文法やプッシュダウン・オートマトンによって文脈自由言語を正しく定義できない |
評価項目4 | □可の基準に加えて再帰的数え上げ可能言語が与えられたとき , そのアルゴリズムを正しく表記できる | □再帰的数え上げ可能言語に対応するチューリング機械 (= 狭義のアルゴリズム ) が与えられたとき , 与えられた語が受理されるか , されないかを追跡できる | □再帰的数え上げ可能言語に対応するチューリング機械 (= 狭義のアルゴリズム ) が与えられたとき , 与えられた語が受理されるか , されないかを追跡できない |
評価項目5 | □再帰的数え上げ可能ではない言語が存在することについて対角線論法を用いた典型的な証明を説明できる | | □再帰的数え上げ可能ではない言語が存在することについて対角線論法を用いた典型的な証明を説明できない |