2026 (Current Year) Faculty Courses School of Engineering Undergraduate major in Information and Communications Engineering

Automata and Languages (ICT)

Academic unit or major: Undergraduate major in Information and Communications Engineering
Instructor(s): Kotaro Funakoshi / Takahiro Shinozaki
Class Format: Lecture/Exercise (Face-to-face)
Media-enhanced courses: -
Day of week/Period (Classrooms): unknown
Class: -
Course Code: ICT.H212
Number of credits: 210
Course offered: 2026
Offered quarter: 3Q
Syllabus updated: Aug 26, 2026
Language: Japanese

Syllabus

Course overview and goals

Students will study formal languages—which form the foundation of programming language processing and natural language processing—from two perspectives: the means of generation and the machines that recognize them. Specific topics covered in the course include phrase-structure grammars, regular expressions, regular grammars, finite automata, context-free grammars, and pushdown automata.

Course description and aims

Keywords

Phrase-structure grammars, regular expressions, regular grammars, finite automata, context-free grammar, pushdown automata, formal languages

Competencies

Specialist skills
Intercultural skills
Communication skills
Critical thinking skills
Practical and/or problem-solving skills

Class flow

We will proceed according to the order of topics listed in the syllabus below. However, the "sessions" indicated in the plan do not correspond directly to specific class dates (there are 14 class days in total); for instance, on Mondays, we may cover two sessions' worth of material during the fourth period. Practical exercises will generally be conducted within the same time slot as the lectures rather than being scheduled on separate days, though there may be days dedicated solely to exercises. The class will be conducted in Japanese.

Course schedule/Objectives

	Course schedule	Objectives
Class 1	Phrase-structure grammars	Understand the topic on the left
Class 2	Regular grammars	Understand the topic on the left
Class 3	Finite state automata	Understand the topic on the left
Class 4	Automata with epsilon-transitions	Understand the topic on the left
Class 5	Minimization of deterministic finite automata	Understand the topic on the left
Class 6	Pumping lemma for regular languages	Understand the topic on the left
Class 7	Regular expressions	Understand the topic on the left
Class 8	Context-free grammars	Understand the topic on the left
Class 9	Chomsky normal form	Understand the topic on the left
Class 10	Pumping lemma for context-free languages	Understand the topic on the left
Class 11	Non-deterministic push-down automata	Understand the topic on the left
Class 12	Equivalence of NPDA and CFG	Understand the topic on the left
Class 13	Properties of context-free grammars	Understand the topic on the left
Class 14	Deterministic push-down automata	Understand the topic on the left

Study advice (preparation and review)

To enhance effective learning, students are encouraged to spend a certain length of time outside of class on preparation and review (including for assignments), as specified by the Tokyo Institute of Technology Rules on Undergraduate Learning (東京科学大学学修規程) and the Tokyo Institute of Technology Rules on Graduate Learning (東京科学大学大学院学修規程), for each class.
They should do so by referring to textbooks and other course material.

Textbook(s)

コンピュータサイエンスのための言語理論入門，R. Smith 著，吉田敬一他訳，共立出版，1986

Reference books, course materials, etc.

オートマトン，言語理論，計算論Ｉ[第2版](Introduction to Automata Theory, Languages, and Computation Second Edition) J. Hopcroft, R. Motowani, J. Ullman 著，野崎昭弘，高橋正子，町田元，山崎秀記訳，サイエンス社，2003

Evaluation methods and criteria

Evaluation will be based on the final examination and exercises.

Related courses

ICT.H217 ： Logic and Reasoning
CSC.T251 ： Automata and Formal Languages
ICT.P204 ： Basic Computer Programming (ICT)
ICT.P208 ： Advanced Computer Programming (ICT)

Prerequisites

N/A