|
|
| 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 | | | 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 aim is to explain the mathematical development of computer science to the student and to provide general information about finite representations of languages ??and the fundamentals of compiler design |
| Learning Outcomes | CTPO | TOA | | Upon successful completion of the course, the students will be able to : | | | | LO - 1 : | Can generate RE, FA, PDA, CFG and TM for defined languages | 1.1 - 1.2 - 3.1 - 3.2 | 1,6, | | LO - 2 : | Can prove that RE and FA , PDA and CFG ??are equivalent | 1.1 - 1.2 - 3.1 - 3.2 | 1,6, | | LO - 3 : | Can establish a connection between theoretical machines and today's computers | 1.1 - 1.2 - 3.1 - 3.2 | 1,6, | | LO - 4 : | Apply mathematical models to solve problems in diverse areas such as string searching, cryptography, and language design. | 1.1 - 1.2 - 3.1 - 3.2 | 1,6, | | 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 ??(Pumping Lemma, Myhill-Nerode Theorem), Decidability. STACK AUTOMATA THEORY: Context-Free Grammars (Trees, Ambiguity), Grammatical Format (Regular Grammars, Chomsky Normal Form, Left-Hand Derivations), Stack Automata, CFG=PDA, Non-Context-Free Languages ??(Pumping Lemma for CFL), Context-Free Languages ??(Closure Properties), CYK Algorithm. TURING THEORY: Turing Machines (TM), Post Machines, Minsky Theorem, TM Types (Motion in State Machine, Halting Option Machine, k-Way TM, Two-Sided Infinite Tape Model, Undetermined TM, Read-Only TM), TM Languages ??(TM Decoding, Universal Turing Machine, Halting Problem). |
| |
| 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 | Sipser, M. 2013; Introduction to Theory of Computation (3rd). | | | |
| Method of Assessment | | Type of assessment | Week No | Date | Duration (hours) | Weight (%) | | Mid-term exam | 9 | | 1,5 | 50 | | End-of-term exam | 16 | | 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 | | Arasınav için hazırlık | 5 | 2 | 10 | | Arasınav | 2 | 1 | 2 | | Dönem sonu sınavı için hazırlık | 5 | 2 | 10 | | Dönem sonu sınavı | 2 | 1 | 2 | | Total work load | | | 80 |
|