Skip to content
Hyper Learning Tech Official Logo
Hyper Learning

AI-Powered Learning Platform

Subject Syllabus

CS-501 - Theory of Computation

CSE · Semester 5

Course Modules

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

Examples of automata machinesFinite automata as a language acceptor and translatorMoore machines and Mealy machinesComposite machineConversion from Mealy to Moore and vice versa
Non-deterministic finite automata (NDFA)Deterministic finite automata machinesConversion of NDFA to DFAMinimization of automata machinesRegular expressionArden's theoremMeaning of union, intersection, concatenation, and closure2-way DFA
Types of grammarContext-sensitive grammarContext-free grammarRegular grammarDerivation treesAmbiguity in grammarSimplification of context-free grammarConversion of grammar to automata machine and vice versaChomsky hierarchy of grammarKilling null and unit productionsChomsky normal form and Greibach normal form
Example of PDADeterministic and non-deterministic PDAConversion of PDA into context-free grammar and vice versaCFG equivalent to PDAPetri net model
Techniques for construction of Turing machinesUniversal Turing machineMultitape, multihead, and multidimensional Turing machineNP-complete problemsDecidability and recursively enumerable languagesDecidability, decidable languages, and undecidable languagesHalting problem of Turing machineThe Post correspondence problem