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 2160704) as prescribed for Computer Engineering · Semester 6 divides the course into 5 units, covering 23 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 (2160704)Unit 1 Review of Mathematical Theory
- Logical statements
- Mathematical induction
- strong principle
- Recursive definitions
Unit 2 Regular Languages and Finite Automata
- Regular expressions
- regular languages
- Automata with output-Moore machine
- Mealy machine
- Finite automata
- memory requirement in a recognizer
- intersection and complement of regular languages.Non Determinism Finite Automata
- Conversion from NFA to FA, - Non Determinism Finite Automata Conversion of NFA- to NFA and equivalence of three Kleene’s Theorem
- Minimization of Finite automata Regular And Non Regular Languages – pumping lemma
Unit 3 Context free grammar (CFG)
- Unions Concatenations And Kleen’s of Context free language Regular grammar
- Derivations and Languages
- Relationship between derivation and derivation trees
- 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, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL
Unit 5 Turing Machine (TM)
- TM Definition
- Model Of Computation And Church Turning Thesis
- computing functions with TM, Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages
- Context sensitive languages and Chomsky hierarchy
Study on Android App:
