AD-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
3 papers, latest Jun 2025
Syllabus, notes and important questions for AD-501
Syllabus units
Topics as the official RGPV syllabus lists them.
Unit 1 Introduction of Automata Theory 9 topics
- Review of Sets
- Mathematical formal proofs including proof by induction and by contradiction
- Introduction to languages, grammars and automata: Alphabet
- Representation of language and grammar
- Types of Automata
- 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 9 topics
- Non Deterministic Finite Automata (NDFA)
- Deterministic finite automata machines
- Conversion of NDFA to DFA
- Minimization of automata machines
- Regular expression
- Applications of regular expressions
- Arden’s theorem
- Meaning of union, intersection, concatenation and closure
- 2‑way DFA
Unit 3 Grammars 10 topics
- Types of grammar
- Context sensitive grammar
- Context free grammar
- Regular grammar
- Derivation trees
- Ambiguity in grammar
- Simplification of context free grammar
- Conversion of grammar to automata machine and vice versa
- Chomsky hierarchy of grammar
- Chomsky normal form and Greibach normal form
Unit 4 Push down Automata 10 topics
- Example of PDA
- Deterministic and non‑deterministic PDAs
- Context Free Grammar
- Parsing
- Ambiguity
- Normal form of CFGs
- CFG to NPDA
- NPDA to CFGs
- CFG equivalent to PDA
- Petri nets model
Unit 5 Turing Machine 11 topics
- Turing Machine as acceptor
- Recognizing a Language
- Universal TMs
- Linear Bounded Automata
- Context Sensitive Languages
- Recursive and Recursively Enumerable Languages
- Unrestricted Grammars
- Halting problem of Turing machine & the post correspondence problem
- Concept of Solvability and Unsolvability
- Church’s Thesis
- Complexity Theory – P and NP problems