Course title
L00210002
Automata and Formal Languages

 PATHAK SARTHAK
Middle-level Diploma Policy (mDP)
Program / Major mDP Goals Courses
Fundamental Mechanical Engineering F 産業界や社会の要請を把握して解決するべき課題を設定し、さまざまな工学分野の知識を関連付けながら設計生産技術を活用することで、立案した構想に従って研究を進め課題を解決することができる。 Sub
Advanced Mechanical Engineering F 産業界や社会の要請を把握して解決するべき課題を設定し、機械工学の学理を応用して異分野を含む融合分野で革新的な機能を創成することができる。 Sub
Environment and Materials Engineering B 地球環境や地域社会との調和を見据えて、さまざまな工学分野に関わる問題を解決することができる。 Sub
Chemistry and Biotechnology B 地球環境や地域社会との調和を見据えて、さまざまな工学分野に関わる問題を解決することができる。 Sub
Electrical Engineering and Robotics D 電気工学や関連する工学の技術分野を課題に適用し、社会の要求を解決するために応用することができる。 Sub
Advanced Electronic Engineering E 専門的デザイン課題について解決する能力を身に付けることができる。 Sub
Information and Communications Engineering F 社会のニーズに対して技術課題を主体的に発見し、工学分野における分野横断的な知識も活用しつつ、計画的・継続的に取り組んで課題を達成することができる。 Sub
Computer Science and Engineering B-1 コンピュータサイエンスの数理的基礎と問題分析のスキルを身に付けることができる。 Main
Urban Infrastructure and Environment G ⼟⽊⼯学における現実の問題について、⼯学・専⾨基礎知識を⽤いて理解・解決することができる。 Sub
Purpose of class
Learning about finite automata and its counterpart, formal language theory, as well as its application to the parsing of programming languages. It has a wide range of applications, including software design and computational complexity theory.
Course description
Finite automata: deterministic, non-deterministic, and those with ε-behavior, and students will understand their behavior while also learning about conversion to deterministic finite automata and minimization. Students will also learn about conversion between regular expressions, the basis of formal languages, and finite automata. Students will also learn how to express context-free languages ​​using BNF and syntax trees, and the equivalence of pushdown automata. This learning approach involves repeatedly solving example problems to understand the meaning of the theory. This course is related to Algorithms and Data Structures, Software Engineering, and Advanced Information Exercise 2B.
Goals and objectives
  1. Being able to read and describe sequential machines
  2. Understand DFA, NFA, and ε-NFA, and be able to transform DFA → regular expression → ε-NFA → NFA → DFA, and be able to minimize DFA
  3. Understands syntax trees and can convert between infix, Polish and reverse Polish notation
  4. Understand the equivalence between context-free grammars and pushdown automata through syntax trees, convert BNF to syntax diagrams
  5. Being able to understand programs that do lexical analysis from regular expressions and syntactic analysis from BNF
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Quizzes In class assignments Programming assignments Total.
1. 10% 5% 15%
2. 10% 5% 15%
3. 10% 5% 15%
4. 10% 5% 15%
5. 40% 40%
Total. 40% 20% 40% -
Evaluation method and criteria
Quizzes (40%), in-class assignments (20%), program assignments (40%)
A total score of 60% or more (a level at which the student can solve textbook problems independently) is required to pass.
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Guidance
Overview: Automata and Language, Chomsky’s Hierarchy 		Syllabus review 90minutes
Revision of study materials 30minutes
2. Formal languages ​​and inductive representations: words, languages, Kleene closures
Sequential machines: Mealy machines, Moore machines 		Textbook pp.22-25，32-39，83-88 90minutes
Revision of study materials 30minutes
3. Sequential Machines: Mealy Machines, Moore Machines (Review and Exercises)
Language Acceptance, Deterministic Automata (DFA) 		Textbook pp. 83-95 90minutes
Revision of study materials 30minutes
4. Regular Expressions Textbook pp. 96-97 90minutes
Revision of study materials 30minutes
5. Linear recursive equations (transformation from DFA)
Nondeterministic automata (NFA) 		Textbook pp. 97-107 90minutes
Revision of study materials 30minutes
6. Conversion to DFA (Subset Construction Method)
ε-NFA: Definition and Conversion to NFA 		Textbook pp.107-112 90minutes
Revision of study materials 30minutes
7. From regular expressions to ε-NFA, NFA, DFA Textbook pp.112-115 90minutes
Revision of study materials 30minutes
8. Minimization (1): Myhill-Nerode theorem, equivalence classes Textbook pp.116-121 90minutes
Revision of study materials 30minutes
9. Minimization (2): Minimization and Exercises
Applications of Finite Automata, Lexical Analysis, Search 		Textbook pp.121-125 90minutes
Revision of study materials 30minutes
Programming assignment: Lexical analysis 360minutes
10. non-regular languages
Formal languages ​​and syntax trees
Formal languages ​​and BNF notation: metalanguages ​​and syntax diagrams 		Textbook pp. 43-47 90minutes
Revision of study materials 30minutes
11. Representation of Formal Languages
Context-Sensitivity and Context-Free Grammars 		Textbook pp.43-47,139-148 120minutes
Revision of study materials 30minutes
Programming assignment: Syntax analysis 480minutes
12. Context-free grammars and parsers
Compilers
Recursive descent 		Textbook pp.148-159，171-177 120minutes
Revision of study materials 30minutes
13. Linear Grammar
LR Algorithm
Compiler-Compiler 		Textbook pp.159-169 120minutes
Revision of study materials 30minutes
14. Pushdown automata
Summary of all topics 		Textbook pp.159-169 90minutes
Revision of study materials 30minutes
Summary of all topics 40minutes
Total. - - 2650minutes
Feedback on exams, assignments, etc.
ways of feedback specific contents about "Other"
Feedback in the class
Textbooks and reference materials
Textbook:
小倉久和著「形式言語とオートマトン入門」コロナ社
大堀淳著　「LR構文解析の原理」　https://www.jstage.jst.go.jp/article/jssst/31/1/31_1_30/_pdf
Prerequisites
Office hours and How to contact professors for questions
  • After class, in the lounge area outside the classroom for about an hour (although sometimes unavailable due to other work).
    Also possible to contact me via email or Slack.
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates a basic problem-solving skills
Active-learning course
More than one class is interactive
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicable
N/A N/A
Education related SDGs:the Sustainable Development Goals
  • 4.QUALITY EDUCATION
  • 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
Last modified : Mon Mar 16 04:02:08 JST 2026