|
|
| COM2004 | Automata Theory | 3+0+0 | ECTS:4 | | Year / Semester | Spring Semester | | Level of Course | First Cycle | | Status | Compulsory | | Department | DEPARTMENT of COMPUTER ENGINEERING | | Prerequisites and co-requisites | None | | Mode of Delivery | Face to face | | Contact Hours | 14 weeks - 3 hours of lectures per week | | Lecturer | Dr. Öğr. Üyesi Selçuk CEVHER | | Co-Lecturer | None | | Language of instruction | | | Professional practise ( internship ) | None | | | | The aim of the course: | | The course aims to provide the students with a general knowledge on a variety of issues in the mathematical development of computer science theory, particularly finite representations for languages and machines, as well as gain a more formal understanding of algorithms and procedures. Applications to compilers, string searching, and control circuit design are discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines are analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course. |
| Learning Outcomes | CTPO | TOA | | Upon successful completion of the course, the students will be able to : | | | | LO - 1 : | Construct RE, FA, PDA, CFG, TM and PM for defined languages. | 1,2,12 | 1 | | LO - 2 : | Prove the equivalence of languages described by FA and RE, the equivalence of languages described by PDA and CFG, the | 1,2,12 | 1 | | LO - 3 : | Make connection between theoretic machines and current computers. | 1,2,12 | 1 | | LO - 4 : | Apply mathematical models to solve problems in diverse areas such as string searching, cryptography, and language design. | 1,2,12 | 1 | | CTPO : Contribution to programme outcomes, TOA :Type of assessment (1: written exam, 2: Oral exam, 3: Homework assignment, 4: Laboratory exercise/exam, 5: Seminar / presentation, 6: Term paper), LO : Learning Outcome | | |
| AUTOMATA THEORY : Languages, Recursive Definitions, Regular Expressions, Finite Automata, Transition Graphs, Kleene's Theorem, Finite Automata with Output, Regular Languages, Nonregular Languages (The Pumping Lemma, Myhill-Nerode Theorem), Decidability. PUSHDOWN AUTOMATA THEORY : Context-Free Grammars (Trees, Ambiguity), Grammatical Format (Regular Grammars, Chomsky Normal Form, Leftmost Derivations), Pushdown Automata, CFG=PDA, Non-Context-Free Languages (The Pumping Lemma for CFLs), Context-Free Languages (Closure Properties), CYK Algorithm. TURING THEORY : Turing Machines (TM), Post Machines, Minsky's Theorem, Variations on the TM (The Move-in-State Machine, The Stay-Option Machine, The k-Track TM, The Two-Way Infinite TAPE Model, The Nondeterministic TM, The Read-Only TM) , TM Languages (The Encoding of Turing Machines, The Universal Turing Machines, Halting Problem), The Chomsky Hierarchy (Phrace-Structure Grammars, Context-Sensitive Grammars), Computers (Computable Functions, Church's Thesis). |
| |
| Course Syllabus | | Week | Subject | Related Notes / Files | | Week 1 | Languages | | | Week 2 | Recursive Definitions | | | Week 3 | Regular Expressions | | | Week 4 | Finite Automata | | | Week 5 | Transition Graphs | | | Week 6 | Kleene's Theorem | | | Week 7 | Finite Automata with Output | | | Week 8 | Regular and Nonregular Languages | | | Week 9 | Mid-term exam | | | Week 10 | Context-Free Grammars | | | Week 11 | Push-Down Automata | | | Week 12 | Turing Machines | | | Week 13 | Post Machines | | | Week 14 | Minsky's Theorem | | | Week 15 | Variations on the TM | | | Week 16 | End-of-term exam | | | |
| 1 | Cohen, D. 1997; Introduction to Computer Theory (2nd). | | | 2 | Sipser, M. 2013; Introduction to Theory of Computation (3rd). | | | |
| 1 | Dersin web sayfası : http://ceng2.ktu.edu.tr/~cakir/otomata.html | | | |
| Method of Assessment | | Type of assessment | Week No | Date | Duration (hours) | Weight (%) | | Mid-term exam | 9 | 05/04/2016 | 1,5 | 50 | | End-of-term exam | 16 | 28/05/2016 | 1,5 | 50 | | |
| Student Work Load and its Distribution | | Type of work | Duration (hours pw) | No of weeks / Number of activity | Hours in total per term | | Yüz yüze eğitim | 3 | 14 | 42 | | Sınıf dışı çalışma | 1 | 14 | 14 | | Laboratuar çalışması | 0 | 0 | 0 | | Arasınav için hazırlık | 5 | 1 | 5 | | Arasınav | 5 | 1 | 5 | | Uygulama | 0 | 0 | 0 | | Klinik Uygulama | 0 | 0 | 0 | | Ödev | 0 | 0 | 0 | | Proje | 0 | 0 | 0 | | Kısa sınav | 0 | 0 | 0 | | Dönem sonu sınavı için hazırlık | 5 | 1 | 5 | | Dönem sonu sınavı | 5 | 1 | 5 | | Diğer 1 | 10 | 5 | 50 | | Diğer 2 | 0 | 0 | 0 | | Total work load | | | 126 |
|