Course Code & Number
CMPE 322
Course Title
Theory of Computation
Credit Hours/ ECTS Credits
(3+0+0) 3 TEDU Credits, 6 ECTS Credits
Mode of Delivery:
Face-to-face
Language of Instruction:
English
Pre-requisite / Co-requisite::
Pre-requisites: CMPE 242
Co-requisites: NONE
Catalog Description
Deterministic finite automata. Non-deterministic finite automata. Regular expressions. Context free grammars. Push down automata. Turing machine. Decidability and undecidability. P and NP classes. Fundamental problems.
Course Objectives
The objective of this course is to provide an understanding of the theory of automata, computability of problems and complexity of computations. Different models of computation will be introduced and their comparisons will be done.
Course Learning Outcomes
Upon succesful completion of this course, a student will be able to
1. understand the functioning of Finite-State Machines, Deterministic Finite-State Automata, Nondeterministic Finite-State Automata and Pushdown Automata;
2. create Automata to accept strings from various simple languages;
3. understand Formal Grammars;
4. discuss the difference between Regular, Context-Free and Context-Sensitive languages;
5. give grammars to produce strings from specific languages.
Learning Activities and Teaching Methods:
Telling/Explaining
Discussion/Debate
Questioning
Reading
Problem Solving
Oral Presentations/Reports
Hands-on Activities
Web Searching
Experiments
Assessment Methods and Criteria:
Test / Exam
Quiz
Case Studies / Homework
Presentation (Oral/Poster)
Assessment Methods and Criteria Others:
Recommended Reading
1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X
2. Peter Linz, An Introduction to Formal Languages and Automata, 3rd Edition.
Required Reading
1. Hopcroft, Motwani, Ullman, Automata Theory, Languages, and Computation 3rd Edition.
Grading
Mid-terms - 20%
Quizzes and Homeworks - 25%
Projects - 20%
Final - 35%
Learning Activities and Teaching Methods Others:
Course & Program Learning Outcome Matching:
