授業科目名				担当教員
言語とオートマトン				鍋島　英知
時間割番号	単位数	コース	履修年次	期別	曜日	時限
263605	2	G	2	前期	火	II
［概要］
記号を扱うコンピュータの論理モデルである有限オートマトン，形式言語，記号処理アルゴリズムについて学ぶ．この学問分野の結果や用語は，言語処理，ソフトウエア，人工知能，パターン認識などに使われておりコンピュータ科学における重要な基礎科目である．<BR><BR>カリキュラム中での位置付け：<a href="http:<BR>//www.cs.yamanashi.ac.jp/g/JABEE/curriculum/">Gコースのカリキュラム</a>
［具体的な達成目標］
離散系の仕組みと各種アルゴリズムの理解（文字列パターンを表現および処理する代数系としての，有限オートマトン・正規表現・文脈自由文法について，文字列の表現，各種アルゴリズムを理解し，応用問題に適用できること）
［必要知識・準備］
先行科目として，基礎離散数学における集合，グラフ，関係，論理設計に関する知識が必要である．またプログラミングIにおけるデータ構造，アルゴリズム，コンパイルに関する知識があると望ましい．同時開講科目であるアルゴリズムとデータ構造では，文字列照合が本講義と深く関係する．
［評価方法・評価基準］
No 評価項目 割合 評価の観点 1 試験：期末期  45  % 文字パターンの再帰記述，文脈自由文法，パース木，文脈自由文法と正規表現，文脈自由文法標準形  2 試験：中間期  45  % 状態，有限オートマトン，状態機械のグラフ表現，決定性と非決定性オートマトン間の変換，正規表現と有限オートマトン間の変換  3 小テスト／レポート  10  % 理解の検証のためのクイズと演習
［教科書］
岩間 一雄, オートマトン・言語と計算理論, コロナ社, ISBN:9784339018219
［参考書］
小倉 久和, 形式言語と有限オートマトン入門, コロナ社, ISBN:9784339023398 J. ホップクロフト, オートマトン言語理論 計算論〈1〉, サイエンス社, ISBN:4781910262
［講義項目］
第1回 言語とは何か・なぜ必要か<BR>第2回 正規表現と有限オートマトン<BR>第3回 非決定性有限オートマトン<BR>第4回 有限オートマトンの等価性（１）DFAとNFA<BR>第5回 有限オートマトンの等価性（2）NFAとε-NFA<BR>第6回 有限ノートマトンと正規表現の等価性 (1)<BR>第7回 有限ノートマトンと正規表現の等価性 (2)<BR>第8回 前半のまとめと中間試験<BR>第9回 UNIX における正規表現<BR>第10回 有限オートマトンの能力の限界と文脈自由文法<BR>第11回 正規言語と文脈自由言語<BR>第12回 文脈自由文法の標準形<BR>第13回 正規文法と文脈自由文法 (1)<BR>第14回 正規文法と文脈自由文法 (2)<BR>第15回 後半のまとめと期末試験
［教育方法］
テキストに従い，より具体的に演習を通じて，各概念，各種変換アルゴリズムの理解を図る．詳細な数学的論証よりは，演習問題による各種表現の変換等に関するアルゴリズムの理解を中心に講義する．演習はまず，講義で示す例題解答を参考に自分や周りの学生同士で解答を試みる努力が必要である．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 情報メディアコース》 (A) マルチメディア情報ネットワーク技術に習熟した情報処理技術者としての基盤となる基礎的素養及び基礎的スキルを修得する。 ◎ (D) 時代の変化に対応できるよう、最新の技術動向を考慮し自律的・継続的に学習する能力を修得する。 ○ (G-4)人間の知性・感性を知り応用するための知性・感性情報工学における基礎的技術 ○
［その他］
(未登録)