AL-601 RGPV B.Tech
Theory of Computation (TOC)
Previous year papers and the official syllabus are free to read, no account needed.
Previous Year Papers
4 papers, latest Jun 2025
Syllabus, notes and important questions for AL-601
Syllabus units
Topics as the official RGPV syllabus lists them.
Unit 1 Introduction to Automata Theory 6 topics
- Examples of automata machines
- Finite Automata as language acceptor and translator
- Moore machines
- Mealy machines
- Composite machine
- Conversion from Mealy to Moore and vice versa
Unit 2 Types of Finite Automata 8 topics
- Non‑deterministic Finite Automata (NFA)
- Deterministic Finite Automata (DFA)
- Conversion of NFA to DFA
- Minimization of automata
- Regular expressions
- Arden’s theorem
- Language operations: union, intersection, concatenation, closure
- Two‑way DFA
Unit 3 Grammars 12 topics
- Types of grammar
- Context‑sensitive grammar
- Context‑free grammar (CFG)
- Regular grammar
- Derivation trees
- Ambiguity in grammar
- Simplification of CFG
- Conversion of grammar to automata and vice versa
- Chomsky hierarchy of grammars
- Elimination of null and unit productions
- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)
Unit 4 Pushdown Automata 6 topics
- Examples of Pushdown Automata (PDA)
- Deterministic PDA
- Non‑deterministic PDA
- Conversion of PDA to CFG and vice versa
- CFG equivalent to PDA
- Petri‑net model for PDA
Unit 5 Turing Machines and Decidability 9 topics
- Construction techniques for Turing machines
- Universal Turing machine
- Multi‑tape, multi‑head and multidimensional Turing machines
- NP‑complete problems
- Decidable and recursively enumerable languages
- Decidability
- Undecidable languages
- Halting problem
- Post correspondence problem
Exam insights
Counted from 4 past AL-601 papers.
Marks asked per paper, by unit
-
Unit 1 Introduction of Automata Theory 12 marks
-
Unit 2 Types of Finite Automata 33 marks
-
Unit 3 Grammars 21 marks
-
Unit 4 Push down Automata 23 marks
-
Unit 5 Turing Machine 23 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
-
Convert a given context-free grammar (CFG) into Greibach Normal Form (GNF).
Asked 3 times: 2025, 2024
-
Derive the regular expression corresponding to a given DFA / finite automaton.
Asked 3 times: 2025, 2024, 2023
-
Differentiate between Mealy and Moore machines (finite state machines with outputs) with a suitable example.
Asked 2 times: 2025, 2024