Skip to content
Hyper Learning Tech Official Logo
Hyper Learning

AI-Powered Learning Platform

Subject Syllabus

AD-501 - Theory of Computation

AIDS · Semester 5

Course Modules

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

Review of setsMathematical formal proofs including proof by induction and by contradictionIntroduction to languages, grammars, and automataAlphabetRepresentation of language and grammarTypes of automataFinite 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 expressionApplications of regular expressionsArden'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 grammarChomsky normal form and Greibach normal form
Example of PDADeterministic and non-deterministic PDAsContext-free grammarParsingAmbiguityNormal form of CFGsCFG to NPDANPDA to CFGsCFG equivalent to PDAPetri nets model
Turing machine as acceptorRecognizing a languageUniversal Turing machinesLinear bounded automataContext-sensitive languagesRecursive and recursively enumerable languagesUnrestricted grammarsHalting problem of Turing machineThe Post correspondence problemConcept of solvability and unsolvabilityChurch's thesisComplexity theory: P and NP problems