Lesson plan / THEORY OF COMPUTATION

Lesson Information

Course Credit 3.0
Course ECTS Credit 5.0
Teaching Language of Instruction İngilizce
Level of Course Bachelor's Degree, TYYÇ: Level 6, EQF-LLL: Level 6, QF-EHEA: First Cycle
Type of Course Compulsory
Mode of Delivery Face-to-face
Does the course require compulsory or optional work experience? Z
Course Coordinator
Instructor (s)
Course Assistant

Purpose and Content

The aim of the course Our graduates; Using professional knowledge and skills as a focus on producing creative solutions to ethical rules; Software experts, business analysts, data analysis specialists, IT consultants, etc., meet the needs of the age in various business fields.
Course Content We have graduated technically competent graduates who adopt technological changes rapidly; They can serve as successful business people in the field of computer engineering and sciences as well as engineers who can make an academic career when necessary.

Weekly Course Subjects

1Finite State Machines, Design, Non-Determinism
2Closure Properties, Regular Expressions, Equivalence with Finite State Machines.
3The Pumping Lemma – Proving a Language is Non-Regular, The Adversary Game, Using Closure Properties.
4Regular Grammars, Equivalence to FSMs, Other FSM Variations, Minimization of FSM’s.
5Decision Algorithms for Regular Sets and Undecidability
6Context-Free Grammars, Semantic and Inductive Design, Examples, Applications.
7Chomsky Normal Form. Three Applications.
8Midterm
9Pushdown Machines, Non-Determinism Adds Power, Equivalence to CFG’s.
10The Pumping Lemma and Non-Context-Free Sets.
11Closure Properties, DCFL’s and Decision Algorithms.
12Turing Machines, Design.
13Variations and Equivalence: Non-Determinism, MultiTape, Two-Way.
14Recursive and Recursively Enumerable Sets, Undecidability.

Resources

1-Introduction to the Theory of Computation, Michael Sipser.