形式言語理論基礎 (120002) Introduction to Formal Language Theory (120002)
 
◇ 担当教員 Instructor : 伊藤 実(Minoru Ito / いとう みのる)
◇ 単位数 Credits : 1単位 ◇ 選択・必修 Required/Elective : 選択 ◇ 講義室 Room : L3
◇ 講義スタイル Style : 講義/公開
◇ 開講時期 Quarter : Ⅰ期 木曜1限

◇ 授業目的 Course goals :  形式言語とオートマトン理論に関する基礎的な知識は,情報科学分野において必須と言える素養である。本講義では,その中で最も基本的な正則言語と有限オートマトンに関する基礎的な事柄を理解することを目的とする。正則言語および有限オートマトンは論理設計,通信プロトコル,情報検索,文字列処理等の多くの分野で必要な概念である。

In this lecture, we will present some of the fundamental issues about regular languages and finite automatons. These knowledge should be essential to study computer science (especially, in logic design, communication protocol, information retrieval and string treatment).
◇ 授業内容 Course description :  計算理論は,情報科学において多くの重要な方法論と結果をもたらした。計算機と同等の能力を持ち,かつ,極限まで簡単化された計算モデルである有限オートマトンを学ぶことで,ハードウェアアーキテクチャの違い,OSの違い,言語の違いにとらわれない,計算機の本質を理解する。同時に,対応する言語のクラスである正則言語も理解する。具体的な項目として,次の順に学んでいく。
 正則言語と有限オートマトン
   ・有限オートマトン(定義,決定性モデルと非決定性モデルの等価性)
   ・正則表現(定義,有限オートマトンとの等価性)
   ・非正則言語(パンピングレンマ)
   ・有限オートマトンの簡単化

Regular Languages and Finite Automatons
- Finite automata (definitions, equivalence between deterministic and nondeterministic models)
- Regular expressions (definitions, equivalence between finite automatons and regular expressions)
- Non-regular languages (pumping lemma)
- Simplification of deterministic finite automatons


◇ 教科書 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 :  アルゴリズムとデータ構造,ブール代数についての知識を持っていることが望ましい。

No specific prerequisition, but 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 : 現在、配布資料はありません。