授業科目名				担当教員
言語とオートマトン				鍋島　英知
時間割番号	単位数	コース	履修年次	期別	曜日	時限
263605	2	G	2	前期	火	I
［概要］
記号を扱うコンピュータの論理モデルである有限オートマトン，形式言語，記号処理アルゴリズムについて学ぶ．この学問分野の結果や用語は，言語処理，ソフトウエア，人工知能，パターン認識などに使われておりコンピュータ科学における重要な基礎科目である．<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
［講義項目］
第１回　ガイダンス，状態，オートマトン<BR>第２回　状態機械のグラフ表現 <BR>第３回　決定性と非決定性<BR>第４回　非決定性から決定性の変換<BR>第５回　正規表現（１）<BR>第６回　正規表現（２）<BR>第７回　正規表現からオートマトンに変換<BR>第８回　前半のまとめと中間試験<BR>第９回　正規表現からオートマトンに変換<BR>第10回　オートマトンから正規表現に変換<BR>第11回　パターンの再帰記述，文脈自由文法<BR>第12回　パース木<BR>第13回　曖昧な文法，文法と正規表現（１）<BR>第14回　文法と正規表現（２），ＣＦＧの標準形<BR>第15回　後半のまとめと期末試験
［教育方法］
テキストに従い，より具体的に演習を通じて，各概念，各種変換アルゴリズムの理解を図る．詳細な数学的論証よりは，演習問題による各種表現の変換等に関するアルゴリズムの理解を中心に講義する．演習はまず，講義で示す例題解答を参考に自分や周りの学生同士で解答を試みる努力が必要である．
［JABEEプログラムの学習・教育目標との対応］
《コンピュータ・メディア工学科 情報メディアコース》 (A) マルチメディア情報ネットワーク技術に習熟した情報処理技術者としての基盤となる基礎的素養及び基礎的スキルを修得する。 ◎ (D) 時代の変化に対応できるよう、最新の技術動向を考慮し自律的・継続的に学習する能力を修得する。 ○ (G-4)人間の知性・感性を知り応用するための知性・感性情報工学における基礎的技術 ○
［その他］
(未登録)