シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
形式言語理論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Formal Language Theory | ||
| 科目番号 /Code |
INS402a INS402c INS402d | ||
| 開講年度 /Academic year |
2023年度 | 開講年次 /Year offered |
2 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
関 新之助 | ||
| 居室 /Office |
西9-513 | ||
| 公開E-mail |
s.seki@uec.ac.jp | ||
| 授業関連Webページ /Course website |
Google classroom (code: qdcyvkf) | ||
| 更新日 /Last update |
2023/03/08 21:37:11 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
形式言語とオートマトンはもともと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. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学（Discrete Mathematics） 論理学（logic） 科目ではないが、ある程度まとまった分量の文章を論理的に構成する能力は必須である。自信のない学生はきちんとした訓練を積んだのちに、改めて履修を検討することを強く勧める。 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. |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
N/A |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書 (Textbook) ・笠井 琢美、岩田 茂樹（著）「有限オートマトン入門」森北出版 For those whose mother tongue is not Japanese, the following book is recommended, which the lecturer actually used to study this field. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson, Addison-Wesley |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
この講義では以下の内容を可能な限り以下の順番で扱う。 This course covers the following topics, hopefully in this order: 1. Introduction: why formal language and automata theory? 2. Preliminaries: machines, languages, problems, and proofs. 3. Formal definition of deterministic finite automaton (DFA) and regular language 4. Non-deterministic finite automata (NFA) 5. Subset construction - Equivalence between DFA and NFA 6. Finite automata with epsilon transitions and removal of such transitions 7. Intermission 1: Grail, a C++ library for automata and expressions 8. Regular expressions 9. Conversion between regular expressions and automata 10. Closure and decision properties of regular languages 11. Algorithm to minimize DFA 12. Intermission 2: Automatic sequence and its application in bioinformatics 13. Pumping lemma: proving languages not to be regular 14. Context-free grammars and languages 15. Chomsky hierarchy |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
担当教員は形式言語およびオートマトンの分野で最も権威のある国際会議の一つ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. |
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
教科書および参考書の演習問題に鋭意取り組むこと。 Try exercises in the textbook and also reference book. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
レポートおよび講義の際の演習問題によって評価する。 You'll be evaluated by the reports and regular exercises in the class. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
定期的なオフィスアワーは設けない。質問がある際にはメールで面談を設定すること。 Regular office hours will not be scheduled. If you have a question, please feel free to make an appointment with the lecturer via emails. |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
主題および達成目標の欄を確認のこと Read the topic and goals. |
| その他 /Others |
N/A |
| キーワード /Keywords |
- Formal language（形式言語） - Finite automaton（有限オートマトン） - Regular expression（正則表現） - Regular language（正則言語） - Non-determinism（非決定性） - Minimization of finite automata（有限オートマトンの最小化） - Grammar（文法） - Chomsky hierarchy（チョムスキー階層） |