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
Papers Coming Soon
We are working hard to add this material. Stay tuned for updates!
Follow on Instagram for UpdatesTheory of Computation Syllabus — Unit-wise Content
The official GTU curriculum for Theory of Computation (subject code BE05000271) as prescribed for AI & ML · Semester 5 divides the course into 7 units, covering 44 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 (BE05000271)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
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
- Backus–Naur Form(BNF)
- Chomsky 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 Cannot Be Accepted, and a Problem That Cannot Be Decided
- Non-Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Undecidable Problems Involving Context-Free Languages
- Post Correspondence Problem
- The Class P and NP
Study on Android App:
