形式言語理論

Google classroom (code: jj2pdz5)

形式言語とオートマトンはもともと40年代から50年代にかけて脳の機能や言語学の分野で提唱された概念であるが、今日の高度情報化社会を支えるインフラとして極めて多岐に渡る役割を果たしている。その中にはコンピュータプログラムの構文解析や安全な情報伝達のためのプロトコル、XMLやTeXなどマークアップ言語の記述やインターネット、AI、遺伝子などの膨大な情報の解析などが含まれる。これらの分野は確かに古典的ではあるが、その習得は将来の収入にも直結するほどきわめて本質的である。本講義ではこれらの分野の基礎を実用例や演習と組み合わせて学ぶ。この講義で学ぶ内容は安全かつ合理的で検証可能なシステムを効率的に設計するための最も重要なツールとなる。

Formal languages and automata, originally proposed to model brain functions and linguistics in 1940's and 50's, serve today as the infrastructure of the modern advanced information society for various purposes of significance such as analyzing computer programs lexically (compiler), securing information exchange by protocols, describing markup languages like XML and TeX, and analyzing enormous amount of data on the Internet, AI, and/or in the gene, to name a few. These fields are certainly classical but essential even in the most immediately monetizable technologies. In this class, you will study the basics of these fields, along with examples and exercises of how they have been used so far and they are used today, so that you will master one of the most essential tools for designing secure, reasonable, and testable systems efficiently.

離散数学(Discrete Mathematics)
論理学(logic)

これらの基礎が出来ているかどうかを最初の講義で試験する。
At the very beginning of this course, you'll be tested on foundation of discrete math and logic to see how likely you can pass this course.

科目ではないが、ある程度まとまった分量の文章を論理的に構成する能力は必須である。自信のない学生はきちんとした訓練を積んだのちに、改めて履修を検討することを強く勧める。
In order to pass this course, you must be capable of writing a considerable amount of texts logically. Without any confidence, you are strongly recommended to improve your logical writing skill first.

N/A

References
・John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson, Addison-Wesley
・笠井 琢美、岩田 茂樹(著)「有限オートマトン入門」森北出版

The lecturer used the textbook by Hopcroft et al. to study this field in Canada.

この講義では以下の内容を可能な限りここに書かれた順番で扱う。但し、教育においては当然のことであるが、内容はレポートや宿題の出来に応じて適宜変更する。
This course covers the following topics, hopefully in this order, but is subject to your performance in the nature of education.

Day1. Introduction: why formal language and automata theory?
2. Turing machine, deterministic finite automaton (DFA), and regular language
3. Non-deterministic finite automata (NFA)
4. Subset construction - Equivalence between DFA and NFA
5. Finite automata with epsilon transitions and removal of such transitions
6. Regular expressions as a finite mean of describing a regular language
7. Simplification of regular expressions
8. Pumping lemmas as a tool to prove languages not to be regular
9. Pumping lemmas as a necessary condition for regularity and as a characterization of regularity
10. Closure and decision properties of regular languages, and cost to their test
11. Algorithm to minimize DFA as an application of equivalence test between states
12. Beyond regularity: Turing machines revisited, and Context-free languages (CFL)
13. Context-free grammars (CFG): their ambiguity and inherency
14. Pushdown automata: a restricted Turing machine as a recognizer of CFL

・In the remaining one class, say 15, I'll introduce you to some cutting-edge applications of formal language theory in nano-scale molecular engineering.

担当教員は形式言語およびオートマトンの分野で最も権威のある国際会議の一つDLTの執行役員を務めている。時間が許せば講義の中で最先端の研究成果を紹介する。

The lecturer is a member of the steering committee of the International Conference on Developments in Language Theory (DLT), which is one of the most highly-esteemed venue for the research on formal language and automata theory. In the intermissions, some of the recent developments in these fields may be introduced.

教科書および参考書の演習問題に鋭意取り組むこと。

Try exercises in the textbook and also reference book.

レポートおよび講義の際の演習問題によって評価する。

You'll be evaluated by the reports and regular exercises in the class.

定期的なオフィスアワーは設けない。質問がある際にはメールで面談を設定すること。

Regular office hours will not be scheduled. If you have a question, please feel free to make an appointment with the lecturer via emails.

主題および達成目標の欄を確認のこと

Read the topic and goals.

N/A