Theory of Computation
Get the full GTU study material, English & Gujarati textbook PDFs, syllabus curriculum, and solved previous year question papers.
English Book & Chapters
English Book Coming Soon
We are working hard to add this material. Stay tuned for updates!
Follow on Instagram for UpdatesGTU Previous Year Papers
Theory of Computation Syllabus — Unit-wise Content
The official GTU curriculum for Theory of Computation (subject code 3164203) as prescribed for CS-AI/ML · Semester 6 divides the course into 7 units, covering 45 listed topics. The unit-wise breakdown below is read from the GTU syllabus document for this subject code, so you can check what the course actually covers before deciding which papers to attempt.
Download the official syllabus PDF (3164203)Unit 1 Review of Mathematical Theory
- Logical statements
- Principal of Mathematical Induction
- Strong Principle
- Recursive Definitions
- Structural Induction
Unit 2 Regular Languages and Finite Automata
- Regular Expressions
- Regular Languages
- Application of Finite Automata
- Automata with output - Moore machine & Mealy machine
- Finite Automata
- Memory requirement in a recognizer
- union- intersection and complement of regular languages
- Non Deterministic Finite Automata
- Conversion from NFA to FA, ^ - Non Deterministic Finite Automata
- Conversion of NFA- ^ to NFA, Kleene’s Theorem
- Minimization of Finite automata
- Regular And Non Regular Languages – pumping lemma
- Subject Code : 3164203 Subject Name : Theory of Computation
Unit 3 Context free grammar (CFG)
- Definitions and Examples
- Unions Concatenations And Kleene’s of Context free language
- Regular Grammar for Regular Language
- Derivations and Ambiguity
- Unambiguous CFG and Algebraic Expressions
- BacosNaur Form (BNF)
- Normal Form – CNF
Unit 4 Pushdown Automata, CFL And NCFL
- Deterministic PDA, Equivalence of CFG and PDA & Conversion
- Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL
Unit 5 Turing Machine (TM)
- TM Definition
- Model Of Computation
- Turing Machine as Language Acceptor
- TM that Compute Partial Function
- Church Turning Thesis
- Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages
- Context sensitive languages and Chomsky hierarchy
Unit 6 Computable Functions
- Partial - Total - Constant Functions
- Primitive Recursive Functions
- Bounded Mineralization
- Regular function
- Recursive Functions
- Minimalization, and μ-Recursive Functions
- All Computable Functions Are μ-Recursive
Unit 7 Un-decidability
- A Language That Can’t Be Accepted, and a Problem That Can’t Be Decided
- Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Undecidable Problems Involving Context-Free Languages
- Post‘s Correspondence Problem
- The Class P and NP
Study on Android App:
