Theory of Computation

Learn and Explore All the Fundamentals of Theory of Computation from Scratch

Theory of Computation

Course Information

This is an introductory course on the theory of computation intended for undergraduate students in computer science. In this course, we will introduce various models of computation and study their power and limitations. We will also explore the properties of corresponding language classes defined by these models and the relations between them. It is designed based on the syllabus given by GATE Computer Science exam.

Why Enroll

Theory of computation is mainly concerned with the study of how problems can be solved using algorithms. These studies are used to understand the way an algorithm is meant to work and to actually prove it work through analyzing problems that may arise with the technique used and finding solutions to these problems. This course will help you to solve the problems which are asked in GATE exam.

Career Prospects

Learning this course will help you to make a career in different fields and positions such as

  1. Lecturer (Computer Science)

  2. Research Engineer

  3. Software Engineer

Course Detail

The Course contains a formal connection between algorithmic problem solving and the theory of languages, automata. It also develops them into a mathematical (and less magical) view towards the algorithmic design and in general computation itself. The course should, in addition, clarify the practical view towards the applications of these ideas in the engineering part of CS. This course will cover the language such as Regular Language, Context Free Language, Context Sensitive Language, and Recursively Enumerable sets. It also covers their corresponding grammar and machine.


GATE Syllabus of TOC
Introduction of Theory of Computation-1
example of language
Deterministic Finite Automata(DFA)
Example of DFA
DFA example2
DFA example 3
DFA Example 4
Operations on DFA
Concatenation Operation
Cross Product Operation
Compelementation Operation
Reversal Operation
Introduction of Non-Deterministic Finite Automata(NDFA)
Examples Of NDFA
Conversion of NDFA To DFA
Example of NDFA Conversion
Complementation of NDFA
Introduction of Epsilon Ndfa
Conversion of Epsilon NDFA to NDFA
Example of Epsilon NDFA Conversion
Introduction To Minimization of DFA
Example of Minimization(DFA)
Introduction of Moore And Mealy Machine
Example of Moore Machine
Example of Mealy Machine
Conversion of Moore To Mealy Machine
Conversion of Mealy To Moore Machine
Introduction To Families of Languages
Families of Languages
Introduction of Regular Expression
Basic Operations on Regular Expression
Example of Regular Expression1
Example of Regular Expression2
Example of Regular Expression3
Identities of Regular Expression
Conversion of Regular Expression To Finite Automata

Theory of Computation