Hiroshima University Syllabus

Back to syllabus main page
Academic Year 2022Year School/Graduate School School of Informatics and Data Science
Lecture Code KA107001 Subject Classification Specialized Education
Subject Name オートマトンと言語理論
Subject Name
Subject Name in
Theory of Automata and Languages
イワモト チュウゾウ
Campus Higashi-Hiroshima Semester/Term 2nd-Year,  First Semester,  1Term
Days, Periods, and Classrooms (1T) Tues1-2,Thur5-6:ENG 103
Lesson Style Lecture Lesson Style
(More Details)
Classroom lecture 
Credits 2.0 Class Hours/Week   Language of Instruction B : Japanese/English
Course Level 2 : Undergraduate Low-Intermediate
Course Area(Area) 25 : Science and Technology
Course Area(Discipline) 02 : Information Science
Eligible Students
Keywords Fundamental concepts of computers, sequential machines, finite automata, and formal language theory 
Special Subject for Teacher Education   Special Subject  
Class Status
within Educational
Criterion referenced
Integrated Arts and Sciences
(Knowledge and Understanding)
・Knowledge and understanding of the importance and characteristics of each discipline and basic theoretical framework.
(Abilities and Skills)
・The ability and skills to collect and analyze necessary literature or data among various sources of information on individual academic disciplines.
・The ability and skills to specify necessary theories and methods for consideration of issues.

Informatics and Data Science Program
(Knowledge and Understanding)
・I1. Knowledge and ability required for collecting and processing high-dimensional data using information processing technologies based on scientific logic, while understanding the theoretical system that forms the basis of informatics.

(Abilities and Skills)
・A. Skills related to the development of an information infrastructure,information processing techniques, and technology for producing new added value through data analysis.

・ B. Ability to identify and solve new problems on their own by quantitative and logical thinking based on data, diverse perspectives, and advanced skills for information processing and analysis.
Class Objectives
/Class Outline
The course introduces some fundamental concepts in automata theory and
formal languages including finite automata, regular expressions,
grammars, and formal languages.  They form basic models of
computation, and they are also the foundation of many branches of
computer science.

Objectives of the class:
1. To understand the basic concept of finite automata.
2. To learn the relationship between regular grammars and finite automata.
3. To study the concept of context-free grammars.
4. To learn the normal forms of grammars and the techniques for simplifying automata.
Class Schedule (1) Mealy and Moore machines
(2) Finite automata
(3) Algorithm to determine whether two machines are equivalent
(4) Minimization algorithms
(5) Nondeterministic finite automata and subset construction
(6) Nondeterministic finite automata with epsilon-moves
(7) Regular sets and regular expressions
(8) Relationship between finite automata and regular expressions
(9) Non-regular languages
(10) Regular grammars and finite automata
(11) Context-free grammar
(12) Simplifying context-free grammars
(13) Chomsky normal form
(14) Greibach normal form
(15) Summary and final exam 
Reference book: 「オートマトン・言語理論 [第2版] 」富田悦次・横森貴著 森北出版 ISBN-13: 978-4627805521 
PC or AV used in
(More Details)  
Learning techniques to be incorporated  
Suggestions on
Preparation and
Prepare for and review every lecture 
Grading Method Final-exam (100%). 
Practical Experience  
Summary of Practical Experience and Class Contents based on it  
Please fill in the class improvement questionnaire which is carried out on all classes.
Instructors will reflect on your feedback and utilize the information for improving their teaching. 
Back to syllabus main page