Theory of Computation

  • College Of Computing & Information Technology |


This course introduces the fundamental mathematical models of computation. The course presents both inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Topics to be covered include Finite automata and regular languages, deterministic and nondeterministic computations, pumping lemma for regular languages, context-free grammars and languages, pushdown automata, pumping lemma for context-free languages, and Turing machines and their variants.


Computer Science bachelor`s degree Program


  • Understand the capabilities and limitation of computational models. Prove whether a given language is regular. Prove whether a given language is context-free. Design variants of Turing machines. Understand the relationship between the regular, context-free, and recursively enumerable languages. Implement simple parsers using Finite State Automata and regular expressions.


Michael Sipser, Introduction to the Theory of Computation, Cengage Learning.

Course Content

content serial Description
2Deterministic Finite State Automata part 1
3Deterministic Finite State Automata part 2
4Non-Deterministic Finite State Automata, Equivalence between DFA and NFA
5Regular Expressions
6Non-Regular Languages
7Context-Free Grammars
8Push-Down Automata
9Non-Context Free Languages
10Turing Machines part 1
11Turing Machines part 2
12Variants of Turing Machines
13Complexity Theory Part 1
14Complexity Theory Part 2

Markets and Career

  • Generation, transmission, distribution and utilization of electrical power for public and private sectors to secure both continuous and emergency demands.
  • Electrical power feeding for civil and military marine and aviation utilities.
  • Electrical works in construction engineering.

Start your application

Start The your journey to your new career.