Introduction to Formal Languages and Automaton
About this course
This course introduces the fundamental computation languages, and machine-based and grammatical models of computation. Upon completion of this course, students are expected to have knowledge of regular languages and finite automata, context-free languages and pushdown automata, and related theorems to computation.
This course is taught in English as a part of the SATOM program at Tokyo Metropolitan University. The course materials will be distributed via Kibako.
Textbooks
John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw-Hill, 2015
Schedule
Slot | Topic | Reading |
1 | Basic | Chapters 1.1, 1.2, and 1.3 |
2 | Basic | Chapters 1.4, 1.5, and 1.6 |
3 | Finite Automata | Chapters 2.1 and 2.2 |
4 | Pumping Lemma | Chapters 2.3 and 2.4 |
5 | Minimum FA, Regular Expressions | Chapter 2.5, 2.6, and 3.1 |
6 | NFA, Kleene Theorem | Chapters 3.2, 3.3, 3.4, and 3.5 |
7 | Review | N/A |
8 | CFG, Regular Languages | Chapters 4.1, 4.2, and 4.3 |
9 | Midterm | N/A |
10 | Simplified and Normal Forms | Chapters 4.4, 4.5, |
11 | PDA | Chapter 5 |
12 | Non-CFL | Chapter 6 |
13 | Tuning Machines | Chapter 7 |
14 | Tuning Machines (Cont.) | Chapter 7 |
15 | Review | N/A |
Copyright (C) 2009-2016 Kazuya Sakai, All Right Received.