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.
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.
- 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% | - |
| 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 |
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.
| 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 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 : Fri Feb 21 04:13:16 JST 2025