Cukurova University, Department of Computer Engineering, Balcali campus

Theory of Computation

Undergraduate Course, CuCEng, 2025

Course Objectives

In this course, the main goal is to define the language classes in terms of grammars and automata.

Course Materials

  • Anil Maheshwari and Michiel Smid, Introduction to Theory of Computation, Carleton University, 2012.
  • Michael Sipser, Introduction to the Theory of Computation, 2nd Edition, Thomson Course Technology, Boston, 2006.
  • John C. Martin, Introduction to Languages and the Theory of Computation, 4th Edition, McGraw-Hill, 2011.

Assessment

40% Midterm (exam,tasks,etc.) + 60% Final (exam,tasks,etc.)

Prerequisites

There is no formal prerequisite; however, taking the Discrete Mathematics course beforehand is recommended.

Weekly Schedule

WeekSubjectsLesson
1Discrete Mathematical Structures reviewLesson 1
2Deterministic (DFA) and Non-Deterministic (NFA) Finite AutomataLesson 2
3NFA to DFA, Regular Expressions (RegEx)Lesson 3
4DFA to RegEx, Pumping Lemma for Regular LanguagesLesson 4
5Context-Free Grammars, Chomsky Normal Form (CNF)Lesson 5
6Push-Down Automata (PDA), CNF to PDALesson 6
7Pumping Lemma for Context-Free LanguagesLesson 7
8Midterm exam 
9Turing Machines, Church-Turing ThesisLesson 8
10Non-Deterministic Turing MachinesLesson 9
11Decidable and Undecidable LanguagesLesson 10
12Enumerability and Enumerable LanguagesLesson 11
13Introduction to Complexity Theory, P & NP classesLesson 12
14Non-Deterministic algorithms, NP-Complete Languages 
15Review for Final Exam 

Resources

Below you can find past exam papers.

tc2013f-e.pdf | tc2013m-e.pdf | tc2014f-e.pdf | tc2014m-e.pdf | tc2015f-e.pdf | tc2015p1-e.pdf | tc2015q1a-e.pdf | tc2015q1b-e.pdf | tc2015q2-e.pdf | tc2015q3a-e.pdf | tc2015q3b-e.pdf | tc2016f-e.pdf | tc2016q1a-e.pdf | tc2016q1b-e.pdf | tc2016q2-e.pdf | tc2016q3a-e.pdf | tc2016q3b-e.pdf | tc2017f-e.pdf | tc2017m-e.pdf | tc2018f-e.pdf | tc2018m-e.pdf | tc2019f-e.pdf | tc2019m-e.pdf