Important Topics in Theory of Computation
By BYJU'S Exam Prep
Updated on: September 25th, 2023

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 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 Exam Pattern 2022, Sectional timing, Marking Scheme |
|
Thanks
#DreamStriveSucceed