KA107001 Theory of Automata and Languages

Hiroshima University Syllabus

Japanese

Academic Year 2022Year 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：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
Program
Criterion referenced
Evaluation 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

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

PC or AV used in
Class,etc. 　

(More Details)

Learning techniques to be incorporated 　

Suggestions on
Preparation and
Review Prepare for and review every lecture

Requirements

Grading Method Final-exam (100%).

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	2022Year	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：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 Program
Criterion referenced Evaluation	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
Text/Reference Books,etc.	Reference book: 「オートマトン・言語理論 [第2版] 」富田悦次・横森貴著　森北出版 ISBN-13: 978-4627805521
PC or AV used in Class,etc.
(More Details)
Learning techniques to be incorporated
Suggestions on Preparation and Review	Prepare for and review every lecture
Requirements
Grading Method	Final-exam (100%).
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