計算理論Ⅰ(130001) Theory of Computation Ⅰ(130001)
 
◇ 担当教員 Instructor : 伊藤 実(Minoru Ito / いとう みのる)
◇ 単位数 Credits : 1単位 ◇ 選択・必修 Required/Elective : 選択 ◇ 講義室 Room : L1
◇ 講義スタイル Style : 講義/公開
◇ 開講時期 Quarter : Ⅱ期 木曜1限

◇ 授業目的 Course goals :  形式言語とオートマトン理論に関する基礎的な知識は,情報科学分野において必須と言える素養である。本講義では,形式言語理論基礎で履修した正則言語と有限オートマトンに関する知識を前提として,文脈自由言語とプッシュダウンオートマトンに関する基礎的な事柄を理解することを目的とする。文脈自由言語およびプッシュダウンオートマトンは構文解析,言語処理の元になる概念である。

In this lecture, we will present some of the fundamental issues about context-free languages and pushdown automatons. These knowledge should be essential to study computer science (especially, in syntax analysis and language processing).
◇ 授業内容 Course description :  計算理論は,情報科学において多くの重要な方法論と結果をもたらした。計算機と同等の能力を持ち,かつ,極限まで簡単化された計算モデルであるプッシュダウンオートマトンを学ぶことで,ハードウェアアーキテクチャの違い,OSの違い,言語の違いにとらわれない,計算機の本質を理解する。同時に,対応する言語のクラスである文脈自由言語も理解する。具体的な項目として,次の順に学んでいく。
 文脈自由言語とプッシュダウンオートマトン
   ・文脈自由言語と文脈自由文法(定義,性質,チョムスキー標準形)
   ・パンピングレンマと非文脈自由言語
   ・文脈自由言語に関する決定問題(所属問題)
   ・プッシュダウンオートマトン(定義,性質,文脈自由言語との等価性)

Context-Free Languages and Pushdown Automatons
- Context-free languages and context-free grammars (definitions, properties, Chomsky normal forms)
- Pumping lemma for context-free languages
- Membership problems for context-free languages
- Pushdown automatons (definitons, properties, equivalence between pushdown automatons and context-free languages)


◇ 教科書 Textbook : モバイルコンピューティング研究室のホームページから該当する科目のテキスト(PDFファイル)をダウンロードすること。特に指定しないが,参考書1,2を読むことを勧める。

You can download the text of this lecture (PDF file) through the homepage of Division for Mobile Computing (Ito-lab). References 2 and 3 should be useful for your self-study.

http://ito-lab.naist.jp/mediawiki/index.php/Lecture/ja
◇ 参考書 Reference materials : 1. 丸岡 章 : 計算理論とオートマトン言語理論,サイエンス社,2005
2. M. Sipser: Introduction to the Theory of Computation Second Edition, Course Technology, 2005
3. J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata Theory, Languages, and Computation second edition, Addison-Wesley, 2000
4. 岩間一雄:オートマトン・言語と計算理論,コロナ社,2003
◇ 履修条件 Prerequisites : Ⅰ期の授業「形式言語理論基礎」での講義内容を前提とする。アルゴリズムとデータ構造,ブール代数についての知識を持っていることが望ましい。

The knowledge of lecture "Introduction to Formal Language Theory" which is given in the first term will be needed in this lecture as prerequisition. It is quite desirable to have the knowledge about algorithms and data structures, Bool algebra.
◇ 成績評価 Grading : 試験により評価する。

Evaluation will be based on examination.
◇ オフィスアワー Office Hours : 木曜5限。その他,e-mailにて相談の上随時。

Thursday from 4:50pm to 6:20pm, or by e-mail.
◇ 配布資料 Handouts : 現在、配布資料はありません。