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

SlotTopicReading
1BasicChapters 1.1, 1.2, and 1.3
2BasicChapters 1.4, 1.5, and 1.6
3Finite AutomataChapters 2.1 and 2.2
4Pumping LemmaChapters 2.3 and 2.4
5Minimum FA, Regular ExpressionsChapter 2.5, 2.6, and 3.1
6NFA, Kleene TheoremChapters 3.2, 3.3, 3.4, and 3.5
7ReviewN/A
8CFG, Regular LanguagesChapters 4.1, 4.2, and 4.3
9MidtermN/A
10Simplified and Normal FormsChapters 4.4, 4.5,
11PDAChapter 5
12Non-CFLChapter 6
13Tuning MachinesChapter 7
14Tuning Machines (Cont.)Chapter 7
15ReviewN/A