KA107001 Theory of Automata and Languages

Hiroshima University Syllabus

Japanese

Academic Year 2024Year School/Graduate School School of Informatics and Data Science

Lecture Code KA107001 Subject Classification Specialized Education

Subject Name オートマトンと言語理論

Subject Name
（Katakana）オートマトントゲンゴリロン

Subject Name in
English Theory of Automata and Languages

Instructor IWAMOTO CHUZO

Instructor
(Katakana) イワモト　チュウゾウ

Campus Higashi-Hiroshima Semester/Term 2nd-Year,  First Semester,  1Term

Days, Periods, and Classrooms (1T) Tues1-2,Thur5-6：ECON B255

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
Program
(Applicable only to targeted subjects for undergraduate students)
Criterion referenced
Evaluation
(Applicable only to targeted subjects for undergraduate students) 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.

Computer Science Program
（Knowledge and Understanding）
・D1. Knowledge and ability to understand the theoretical framework underlying computer science and to collect and process high-dimensional data through full use of information processing technology based on scientific logic.
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Data Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Intelligence Science Program
（Knowledge and Understanding）
・D1. A deep systematic understanding of the advanced intelligence of human beings and its realization by computers.
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Class Objectives
/Class Outline    Automata and Formal Language Theory are foundational concepts in
the field of information science.  Automata serve as the simplest
abstract models of computers, while formal languages provide the
mathematical models for programming languages.  These concepts are
used to express the theoretical structure of various problems in
computer science and to formalize systems.
   To pursue the design and development of computers, it is essential
to understand and apply the background knowledge and theories.  For
instance, a logical understanding of the principles of computation in
current computers requires knowledge of automaton theory.
Additionally, understanding the theory of formal languages plays a
crucial role in presenting desired computations to computers and
instructing the computational procedures.
   This course aims to explain the most fundamental concepts related
to computers in an easily understandable manner.  The key objectives
include:
1.Understand the basic concepts of finite automata.
2.Learn the relationship between regular grammars and finite automata.
3.Understand the concept of context-free grammars.
4.Acquire the skills for designing automata and formal grammars.

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

Text/Reference
Books,etc. 「オートマトン・言語理論（第2版・新装版）」富田悦次・横森貴著　森北出版 ISBN-13: 978-4627805538

PC or AV used in
Class,etc. 　

(More Details)

Learning techniques to be incorporated 　

Suggestions on
Preparation and
Review From Session 1 to Session 15, individual tasks to be worked on will be
assigned during the class.

Requirements

Grading Method Evaluation will be based on the final exam.  Passing grade is 60 points or above.

Practical Experience

Summary of Practical Experience and Class Contents based on it

Message

Other

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.

Academic Year	2024Year	School/Graduate School	School of Informatics and Data Science
Lecture Code	KA107001	Subject Classification	Specialized Education
Subject Name	オートマトンと言語理論
Subject Name （Katakana）	オートマトントゲンゴリロン
Subject Name in English	Theory of Automata and Languages
Instructor	IWAMOTO CHUZO
Instructor (Katakana)	イワモト　チュウゾウ
Campus	Higashi-Hiroshima	Semester/Term	2nd-Year, First Semester, 1Term
Days, Periods, and Classrooms	(1T) Tues1-2,Thur5-6：ECON B255
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 Program (Applicable only to targeted subjects for undergraduate students)
Criterion referenced Evaluation (Applicable only to targeted subjects for undergraduate students)	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. Computer Science Program （Knowledge and Understanding）・D1. Knowledge and ability to understand the theoretical framework underlying computer science and to collect and process high-dimensional data through full use of information processing technology based on scientific logic. （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. Data Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. Intelligence Science Program （Knowledge and Understanding）・D1. A deep systematic understanding of the advanced intelligence of human beings and its realization by computers. （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.
Class Objectives /Class Outline	Automata and Formal Language Theory are foundational concepts in the field of information science. Automata serve as the simplest abstract models of computers, while formal languages provide the mathematical models for programming languages. These concepts are used to express the theoretical structure of various problems in computer science and to formalize systems. To pursue the design and development of computers, it is essential to understand and apply the background knowledge and theories. For instance, a logical understanding of the principles of computation in current computers requires knowledge of automaton theory. Additionally, understanding the theory of formal languages plays a crucial role in presenting desired computations to computers and instructing the computational procedures. This course aims to explain the most fundamental concepts related to computers in an easily understandable manner. The key objectives include: 1.Understand the basic concepts of finite automata. 2.Learn the relationship between regular grammars and finite automata. 3.Understand the concept of context-free grammars. 4.Acquire the skills for designing automata and formal grammars.
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
Text/Reference Books,etc.	「オートマトン・言語理論（第2版・新装版）」富田悦次・横森貴著　森北出版 ISBN-13: 978-4627805538
PC or AV used in Class,etc.
(More Details)
Learning techniques to be incorporated
Suggestions on Preparation and Review	From Session 1 to Session 15, individual tasks to be worked on will be assigned during the class.
Requirements
Grading Method	Evaluation will be based on the final exam. Passing grade is 60 points or above.
Practical Experience
Summary of Practical Experience and Class Contents based on it
Message
Other
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