CS-501 RGPV B.Tech
Theory of Computation (TOC)
Previous year papers and the official syllabus are free to read, no account needed.
Previous Year Papers
6 papers, latest Dec 2025
- CS-501 paper, Dec 2025
- CS-501 paper, Jun 2025
- CS-501 paper, Dec 2024
- CS-501 paper, Nov 2023
- CS-501 paper, May 2023
- CS-501 paper, Nov 2022
Syllabus, notes and important questions for CS-501
Syllabus units
Topics as the official RGPV syllabus lists them.
Unit 1 Introduction of Automata Theory 5 topics
- Examples of automata machines
- Finite Automata as a language acceptor and translator
- Moore machines and Mealy machines
- Composite machine
- Conversion from Mealy to Moore and vice versa
Unit 2 Types of Finite Automata 6 topics
- Non‑Deterministic Finite Automata (NDFA)
- Deterministic Finite Automata (DFA)
- Conversion of NDFA to DFA
- Minimization of automata machines
- Regular expressions and Arden’s theorem
- Union, intersection, concatenation and closure; 2‑way DFA
Unit 3 Grammars 4 topics
- Types of grammar: context‑sensitive, context‑free, regular
- Derivation trees, ambiguity, simplification of context‑free grammar, conversion of grammar to automata and vice versa
- Chomsky hierarchy, killing null and unit productions
- Chomsky normal form and Greibach normal form
Unit 4 Push‑down Automata 4 topics
- Examples of PDA, deterministic and non‑deterministic PDA
- Conversion of PDA into context‑free grammar and vice versa
- CFG equivalent to PDA
- Petri‑net model
Unit 5 Turing Machine 2 topics
- Techniques for construction; Universal Turing machine, multitape, multi‑head and multidimensional Turing machines, NP‑complete problems
- Decidability and recursively enumerable languages; decidable, undecidable languages, halting problem, Post correspondence problem
Unit 6 == END OF UNITS==
The syllabus lists no separate topics for this unit.
Exam insights
Counted from 6 past CS-501 papers.
Marks asked per paper, by unit
-
Unit 1 Introduction of Automata Theory 9 marks
-
Unit 2 Types of Finite Automata 28 marks
-
Unit 3 Grammars 27 marks
-
Unit 4 Push down Automata 18 marks
-
Unit 5 Turing Machine 28 marks
Average marks of the questions from each unit in one paper. You answer only some of them, so the total is more than the paper’s maximum.
Asked again and again
-
What is the halting problem and prove/explain why it is undecidable
Asked 4 times: 2025, 2023, 2022
-
Write a regular expression for a given language description over an alphabet (e.g., containing a substring, ending with a pattern, with a count condition).
Asked 3 times: 2025, 2023, 2019
-
Explain pushdown automata and compare deterministic PDA (DPDA) and non-deterministic PDA (NPDA) with a suitable example, including whether they are equivalent.
Asked 3 times: 2025, 2024, 2023