Important Topics in Theory of Computation

By Kajal Vats|Updated : July 29th, 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

Languages

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

Grammars 

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

Properties

  • 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 Gradeup Green Card check the following link:

Click Here to Avail GATE CSE Green Card! (100+ Mock Tests)

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

Click here to avail Super 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

Thanks

Prep Smart. Score Better!

Posted by:

Kajal VatsKajal VatsMember since Apr 2020
Share this article   |

Comments

write a comment

Follow us for latest updates