| 授業の目的 【日本語】 | | |
|
| 授業の目的 【英語】 | | | We study the basics of automata and formal languages, which are fundamental theories of information processing such as automatic operation and data processing. Goal of this class is to understand basic notions of the theory, and be able to explain them, to understand transformations between different languages, and be able to perform them, and to understand proofs of basic theorems, and be able to prove simple problems. |
|
|
| 到達目標 【日本語】 | | | オートマトン理論・形式言語理論とは抽象的な計算装置の理論であり，情報処理全般の理論的基礎であるとともに，コンピュータ科学の多くの教科における本質的な道具である。本講義では，これらの理論の基本概念を理解し説明できること，異なる言語の表現間の変換を理解し計算できること，基本的な定理の証明を理解し簡単な問題の証明に応用できることを目的とする。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | オートマトン理論の基本的事項である，オートマトン，正規表現，文脈自由文法，プッシュダウンオートマトンなどを学ぶ。
1. 基本事項の確認
2. 有限オートマトン
3. NFAとDFAの能力の等価性
4. 正規表現とその性質
5. 有限オートマトンの最小化
6. 文脈自由文法
7. プッシュダウンオートマトン
| |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 演習の評価30％，中間試験30％，期末試験40％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | 授業で用いるスライドのハンドアウトをWEB上に用意する。「離散数学及び演習」を受講していることが望ましい。
教科書：J. ホップクロフト／J. ウルマン「オートマトン 言語理論 計算論Ｉ」，野崎明弘ら訳，サイエンス社，ISBN 4-7819-0374-X | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 演習で解いた課題および宿題の解答例をWEB上に掲載し，自習による理解を促す。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|