Course title
V0530000
Automata

 idogawa tomoyuki Click to show questionnaire result at 2017
Course description
Automaton is one of the mathematical models of computation. In this lecture, the definitions and theories of deterministic/nondeterministic finite automata will be introduced and the relation between them and computational theories will be talked. Each automaton is an abstract machine which recognizes a certain formal language. The introductory theories of formal languages and the fundamentals of programming will be also discussed.
Purpose of class
To study one of the mathematical models "Automaton," which is used to discuss "what is computation" mathematically, and to understand the introductory concepts of "computation theory."
Goals and objectives
  1. Understand the difference between DFA and NFA and the equivalence of them from the viewpoint of language recognizers.
  2. Understand the relation between automata and languages.
  3. Understand the relationship among classes of languages.
Language
Japanese(English accepted)
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Preliminaries 1 (sets/functions and relations) Review the elementary set theory 190minutes
2. Preliminaries 2 (graphs/strings and languages) Review the last lecture/read handouts 190minutes
3. Deterministic finite automata (DFA) Review the last lecture/read handouts 190minutes
4. Regular languages (RL) Review the last lecture/read handouts 190minutes
5. Nondeterministic finite automata (NFA) Review the last lecture/read handouts 190minutes
6. Equivalence of DFA and NFA Review the last lecture/read handouts 190minutes
7. Regular expressions (REX) and RL Review the last lecture/read handouts 190minutes
8. Equivalence of REX and RL, examples of RL Review the last lecture/read handouts 190minutes
9. Pumping lemma for RL and non-regulra languages Review the last lecture/read handouts 190minutes
10. Context free grammars (CFG) and context-free languages (RL) Review the last lecture/read handouts 190minutes
11. Ambiguity of grammars and Chomsky normal form Review the last lecture/read handouts 190minutes
12. Pushdown automata (PDA) Review the last lecture/read handouts 190minutes
13. Equivalence of CFG and PDA Review the last lecture/read handouts 190minutes
14. Final examination and review Review the total lectures/read handouts 190minutes
Total. - - 2660minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Examination Report Total.
1. 20% 10% 30%
2. 30% 10% 40%
3. 20% 10% 30%
Total. 70% 30% -
Evaluation method and criteria
Examinations (70%) and reports (30%)
Textbooks and reference materials
Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013; handout will be available
Prerequisites
Discrete mathematics, fundamental knowledge/technique of computer programming
Office hours and How to contact professors for questions
  • Tuesday 12:15 -- 13:00
Relation to the environment
Non-environment-related course
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Non-social and professional independence development course
Active-learning course
N/A
Last modified : Wed Oct 17 07:34:00 JST 2018