| Program / Major | mDP | Goals |
|---|---|---|
| Mathematical Sciences Course | DP-4・2 | キャリアを見据えた高度な専門知識 現象の背後にある数理構造やデータのパターンを理論的に解析し、社会や自然科学、工学における複雑な課題に対して数理的視点から解決戦略を提案できる。 |
To study about ”finite automata,” which are mathematical models used to discuss ”what is computation” mathematically, and
to understand the fundamental concepts of ”theory of computation.” In addition, to learn about formal languages, which are
the counterpart of finite automata.
The object of the theory of computation is computation itself. The Turing machine is a typical mathematical model of computation.
In this lecture, finite automata, which can be regarded as a limited version of the Turing machine, will be introduced and
its relation to the theory of computation will be explained. Each automaton is an abstract machine which recognizes a certain
formal language. So the introductory theories of formal languages and the fundamentals of programming will be also discussed.
- Understand the difference between DFA and NFA and the equivalence of them from the viewpoint of language recognizers.
- Understand the relation between automata and languages.
- Understand the relationship among classes of languages.
| Term-end examination | Usual assignments | Total. | |
|---|---|---|---|
| 1. | 20% | 15% | 35% |
| 2. | 30% | 15% | 45% |
| 3. | 10% | 10% | 20% |
| Total. | 60% | 40% | - |
Term-end examination (60%) and two or three regular assignments (40%).
Submit each report in the specified format on time. Complete the assigned tasks without fail (correct results for calculations, and correct deductions for proofs). When a discussion is required, write a discussion, not an impression. The report should be written with the reader in mind (in principle, the process should be written as well as the answer). You will get 100 points if you have done these things perfectly. You will be given a halfway point for each report, so if you achieve 60% of the above, you will pass.
Submit each report in the specified format on time. Complete the assigned tasks without fail (correct results for calculations, and correct deductions for proofs). When a discussion is required, write a discussion, not an impression. The report should be written with the reader in mind (in principle, the process should be written as well as the answer). You will get 100 points if you have done these things perfectly. You will be given a halfway point for each report, so if you achieve 60% of the above, you will pass.
| 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) | Study about graphs and languages in advance. | 190minutes |
| 3. | Deterministic finite automata (DFA) | Review the last lecture/read handouts. | 190minutes |
| 4. | Regular languages (RL), strings and languages, review the definition of DFA | 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-regular languages | Review the last lecture/read handouts. | 190minutes |
| 10. | Context free grammars (CFG) and context free languages (CFL) | 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 |
| ways of feedback | specific contents about "Other" |
|---|---|
| Feedback in the class |
Handout will be available.
Reference: M. Sipser, ”Introduction to the theory of computation 3rd editon,” Cengage Learning, 2013.
Reference: M. Sipser, ”Introduction to the theory of computation 3rd editon,” Cengage Learning, 2013.
It is recommended to be familiar with the set theory and logical symbols studied in ”Fundamentals of Mathematics” and so on.
It is also recommended to take ”Data Structures and Algorithms”.
- Course that cultivates an ability for utilizing knowledge
| Work experience | Work experience and relevance to the course content if applicable |
|---|---|
| N/A | N/A |
Last modified : Mon Mar 23 04:07:34 JST 2026