Course Code & Number
CMPE 322
Course Title
Theory of Computation
Level
BS
Credit Hours/ ECTS Credits
(3+0+0) 3 TEDU Credits, 6 ECTS Credits
Year of Study:
Junior
Semester:
Fall
Type of Course:
Elective
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.
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.