授業科目名	オートマトンと言語
時間割番号	263222KA
担当教員名	鈴木 良弥
開講学期・曜日・時限	前期・水・I	単位数	2
＜対象学生＞
コンピュータ・メディア工学科以外
＜授業の目的および概要＞
本科目は情報科学における基礎をなし，ソフトウェア作成においても基礎的な知識として重要なものである．グラフ理論，有限オートマトン，形式言語理論，計算論を学び，ソフトウェア作成などに役立てる．
＜到達目標＞
簡単な数式などから構文木を書くことが出来る．<BR>状態遷移図から正規表現へ，正規表現から状態遷移図に変換できる．<BR>字句パターンを正規表現で表現できる．<BR>正規表現から状態数最小の有限オートマトンを構成できる．<BR>プッシュダウンオートマトンの動作を理解できる．
＜授業の方法＞
毎回簡単な演習を行う．<BR>授業資料はWebで公開する．<BR>中間試験，期末試験の解答例をWebで公開する．
＜成績評価の方法＞
No 評価項目 割合 評価の観点 1 試験：定期試験  57  % 授業理解力  2 試験：中間試験  30  % 授業理解力  3 小テスト／レポート課題  13  % 自発的勉学
＜受講に際して・学生へのメッセージ＞
他学科の学生にも理解しやすい授業を目指します．
＜テキスト＞
形式言語と有限オートマトン入門　　例題を中心とした情報の離散数学, コロナ社, ISBN:4339023396
＜参考書＞
(未登録)
＜授業計画の概要＞
１．数学的準備（集合と写像　記号論理），帰納的表現<BR>　　　２．形式言語<BR>　　　３．離散グラフ<BR>　　　４．木グラフ<BR>　　　５．有限オートマトン１<BR>　　　６．有限オートマトン２<BR>　　　７．正規表現１<BR>　　　８．正規表現２<BR>　　　９．中間試験<BR>　　１０．有限オートマトンの最小化<BR>　　１１．プッシュダウンオートマトン<BR>　　１２．チューリング機械<BR>　　１３．形式言語理論<BR>　　１４．文脈自由文法