# 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.

## 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 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

Thanks

#DreamStriveSucceed

write a comment

### GATE & PSU CS

Computer ScienceGATEGATE CSENIELITOther ExamsQuick LinksMock Test

Follow us for latest updates

GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com