Theory of Computation 3160704 Syllabus Download With Weightage

Theory of Computation 3160704 Syllabus Download With Weightage

Theory of Computation 3160704 is a term that refers to Computer Department covers this subject This year, this Subject is covered in the 6th Semester.   

Sr. No.

Review of Mathematical Theory:

Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of
Mathematical Induction, Strong Principle, Recursive Definitions, Structural


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, Definitions, 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.


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


Pushdown Automata, CFL And NCFL:

Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion,
Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL.


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.


Computable Functions:

Partial – Total – Constant Functions, Primitive Recursive Functions, Bounded
Mineralization, Regular function, Recursive Functions, Quantification,
Minimalization, and μ-Recursive Functions, All Computable Functions Are μRecursive


Undecidability :

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




Tap the Download Button to get the Syllabus of Theory of Computation 3160704 With Weightage. Download now 

Thank you for taking the time to come see us.

You have visited to get GTU B.E. Computer Department SEM 6 Syllabus of Theory of Computation 3160704

Along with the GTU B.E. Computer department SEM 6th  Syllabus, we provide a variety of other resources on We provide GTU papers for all branches, as well as subject-specific Gtu Papers, MCQs, and notes.

Leave a Comment