• No products in the cart.

The Theory of Computation is a scientific discipline concerned with the study of general properties of computation be it natural, man-made, or imaginary. Most importantly, it aims to understand the nature of efficient computation. The [course_title] is designed to introduce various models of computation and study your power and limitations. This course covers the theoretical computer science areas of formal languages and automata, computability and complexity. 


This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.


Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of the assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.

Having an Official Edukite Certification is a great way to celebrate and share your success. You can:

  • Add the certificate to your CV or resume and brighten up your career
  • Show it to prove your success


Course Credit: Open Culture 

Course Curriculum

L1: Introduction to Finite-State Machines and Regular Languages 01:06:00
L2: Regular Languages and Non-Deterministic FSMs 01:21:00
L4: Regular Expressions 01:19:00
L5: Regular Expressions, Regular Languages and Non-Regular Languages 01:18:00
L6: The Pumping Lemma and Introduction to CFLs 01:17:00
L7: Contex-Free Grammars and Push-Down Automata 01:19:00
L8: Introduction to Turing Machines and Computations 01:15:00
L9: More TM Design and Introduction to Non-Determinstic TMs 01:20:00
L10: Equivalence of Non-Deterministic and Deterministic TMs 01:16:00
L11: Church-Turing Thesis and Examples of Decidable Languages 01:18:00
L12: Universal Turing Machines; The Halting Problem is Recognizable but Not Decidable 01:19:00
L13: Diagonalization, Countability and Uncountability 01:13:00
L14: More Diagonalization; Proof that Turing Machines are Countable 00:11:00
L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable 00:25:00
L16: Unrecognizable Languages and Reductions 00:40:00
L17: Using Reductions to Prove Language Undecidable 00:54:00
L18: More Complex Reductions 01:15:00
L19: Uncomputable Functions, and Introduction to Complexity 01:21:00
L20: P, NP and Polynomial-Time Reductions 00:33:00
L21: NP-Completeness 01:12:00
L25: Minimizing Finite State Machines 01:14:00
L26: Minimizing the Number of States in a DFA 01:26:00
Submit Your Assignment 00:00:00
Certification 00:00:00

Course Reviews


9 ratings
  • 5 stars0
  • 4 stars0
  • 3 stars0
  • 2 stars0
  • 1 stars0

No Reviews found for this course.

©2021 Edukite. All Rights Resereved
Edukite is A Part Of Ebrahim College, Charity Commission
Reg No 110841