Skip to content
Hyper Learning Tech Official Logo
Hyper Learning

AI-Powered Learning Platform

Subject Syllabus

CSIT-503 (A) - Theory of Computation

CSIT · Semester 5

Course Modules

Learn topic-wise with Hyper AI and revise using mapped PYQs.

Introduction of the theory of computationFinite state automata: description of finite automataProperties of transition functionsTransition graphDesigning finite automataFSM, DFA, and NFA2-way finite automataEquivalence of NFA and DFAMealy and Moore machines
Regular grammarsRegular expressionsRegular setsClosure properties of regular grammarsArden's theoremMyhill-Nerode theoremPumping lemma for regular languagesApplication of pumping lemmaApplications of finite automataMinimization of FSA
Introduction of context-free grammarDerivation treesAmbiguitySimplification of CFGsNormal forms of CFGs: Chomsky Normal Form and Greibach Normal FormPumping lemma for CFLsDecision algorithms for CFGsDesigning CFGsClosure properties of CFLs
Introduction of PDAFormal definitionClosure property of PDAExamples of PDADeterministic pushdown automataNPDAConversion of PDA to CFGConversion of CFG to PDA
Turing machines: basics and formal definitionLanguage acceptability by TMExamples of TMVariants of TMs: multitape TM, NDTM, Universal Turing Machine, and offline TMsEquivalence of single-tape and multitape TMsRecursive and recursively enumerable languagesDecidable and undecidable problems with examplesHalting problemReducibilityIntroduction of P, NP, NP-complete, and NP-hard problems with examples