Important Topics in Theory of Computation

By Kajal Vats|Updated : October 5th, 2021

Theory of Computation comes under the core subjects of Computer Science. This subject carries a good amount of weightage in the GATE exam and all PSU's exams and also this subject is quite scoring. So, here in this article, we are going to provide a list of important topics on this subject. While preparing for this subject, we advise you to not miss any of these topics because they are asked for the maximum time in GATE and other exams. 

Table of Content

Topic in Theory of Computation

Regular Expressions

  • Properties of Regular Expressions
  • Arden's Theorem

Finite Automata

  • Finding the minimum number of states
  • Minimizing a DFA
  • NFA to DFA conversion
  • Complementing a DFA
  • Reversing a DFA
  • Myhill - Nerode Theorem
  • Pumping Lemma for Regular Languages
  • Compound Automata
  • Mealy and Moore Machines


  • Identifying regular
  • Identifying CFL
  • Identifying DCFL
  • Identifying CSL


  • 4 types of grammars
  • Chomsky Normal Form
  • Ambiguity Test


  • Closure Properties
  • Decidable Properties

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, ISRO, DRDO, BARC, NIELIT, etc. with the BYJU'S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Important Links

GATE CSE Question Papers

GATE CSE Study Plan

GATE CSE Exam Analysis

GATE Study Material for CSE

GATE CSE Exam Pattern 2022, Sectional timing, Marking Scheme

ISRO EC Question Papers

GATE CSE Syllabus 2022

ISRO EC Study Plan

ISRO EC Syllabus




write a comment

Follow us for latest updates