IT-503 (A) RGPV B.Tech
Theory of Computation (TOC)
Previous year papers and the official syllabus are free to read, no account needed.
Previous Year Papers
3 papers, latest Jun 2025
Syllabus, notes and important questions for IT-503 (A)
Syllabus units
Topics as the official RGPV syllabus lists them.
Unit 1 Finite State Automata 11 topics
- Introduction to the theory of computation
- Description of finite automata
- Properties of transition functions
- Transition graph design
- Designing finite automata (FSM)
- Deterministic Finite Automaton (DFA)
- Nondeterministic Finite Automaton (NFA)
- Two‑way finite automata
- Equivalence of NFA and DFA
- Mealy machines
- Moore machines
Unit 2 Regular Languages and Expressions 10 topics
- Regular grammars
- Regular expressions
- Regular sets
- Closure properties of regular grammars
- Arden’s theorem
- Myhill‑Nerode theorem
- Pumping lemma for regular languages
- Applications of the pumping lemma
- Applications of finite automata
- Minimization of finite state automata
Unit 3 Context‑Free Grammars 10 topics
- Introduction to context‑free grammar (CFG)
- Derivation (parse) trees
- Ambiguity in CFGs
- Simplification of CFGs
- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)
- Pumping lemma for context‑free languages
- Decision algorithms for CFGs
- Designing CFGs
- Closure properties of CFLs
Unit 4 Pushdown Automata 8 topics
- Introduction to pushdown automata (PDA)
- Formal definition of PDA
- Closure properties of PDA
- Examples of PDA
- Deterministic pushdown automata (DPDA)
- Nondeterministic pushdown automata (NPDA)
- Conversion from PDA to CFG
- Conversion from CFG to PDA
Unit 5 Turing Machines and Complexity 12 topics
- Basics and formal definition of Turing machines (TM)
- Language acceptability by TM
- Examples of Turing machines
- Multitape Turing machines
- Nondeterministic Turing machines (NDTM)
- Universal Turing machine
- Offline Turing machines
- Equivalence of single‑tape and multitape TMs
- Recursive and recursively enumerable languages
- Decidable and undecidable problems
- Halting problem and reducibility
- Complexity classes: P, NP, NP‑complete, NP‑hard
Exam insights
Counted from 3 past IT-503 (A) papers.
Marks asked per paper, by unit
-
Unit 1 Introduction of the theory of computation 23 marks
-
Unit 2 Regular grammars and Expressions 16 marks
-
Unit 3 Introduction of Context-Free Grammar 28 marks
-
Unit 4 Introduction of PDA 21 marks
-
Unit 5 Turing machines 21 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
-
Explain the Turing machine model, including its formal tuple definition, components, working of the read/write head, and its representations.
Asked 4 times: 2024, 2020
-
Derive the regular expression accepted by a given DFA / finite automaton.
Asked 3 times: 2025, 2024, 2022
-
Construct an equivalent finite automaton / DFA directly from a given regular expression.
Asked 3 times: 2025, 2024, 2020