Course Code & Number
CMPE 327
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:
Compulsory
Mode of Delivery:
Face-to-face
Language of Instruction:
English
Pre-requisite / Co-requisite:
Pre-requisites: CMPE 242 OR CMPE 223
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 enable students understand the theory of automata, computability of problems and complexity of computations. The course presents different models of computation and includes their comparison
Course Learning Outcomes
Upon successful completion of this course, students will be able to;
- Construct deterministic finite state automata (DFA), non-deterministic finite state automata (NFA) with epsilon transition,
- Apply epsilon elimination to NFAs,
- Employ Kleene Algebra Axioms in regular expression (REGEXP) simplification problems,
- Demonstrate the ability of normalizing CFGs into Chomsky and Greibach Normal Forms,
- Design TMs that recognize recursively enumerable languages constructed by unrestricted grammars.
Course Coordinator:
Dr. Fırat Akba