Theory of Computation detailed syllabus for CSE (IOT) (CSEIOT) for 2022-23 regulation curriculum has been taken from the Rajasthan Technical University official website and presented for the cse (iot) students. For course code, course name, number of credits for a course and other scheme related information, do visit full semester subjects post given below.
For CSE (IOT) 4th Sem scheme and its subjects, do visit CSEIOT 4th Sem 2022-23 regulation scheme. The detailed syllabus of theory of computation is as follows.
Contents and Hours
- Introduction: Objective, scope and outcome of the course. 1
- Finite Automata & Regular Expression: Basic machine, Finite state machine, Transition graph, Transition matrix, Deterministic and non-deterministic finite automation, Equivalence of DFA and NDFA, Decision properties, minimization of finite automata, Mealy & Moore machines. Alphabet, words, Operations, Regular sets, relationship and conversion between Finite automata and regular expression and vice versa, designing regular expressions, closure properties of regular sets, Pumping lemma and regular sets, Myhill- Nerode theorem , Application of pumping lemma, Power of the languages. 7
- Context Free Grammars (CFG), Derivations and Languages, Relationship between derivation and derivation trees, leftmost and rightmost derivation, sentential forms, parsing and ambiguity, simplification of CFG, normal forms, Greibach and Chomsky Normal form , Problems related to CNF and GNF including membership problem. 8
- Nondeterministic PDA, Definitions, PDA and CFL, CFG for PDA, Deterministic PDA, and Deterministic PDA and Deterministic CFL , The pumping lemma for CFL’s, Closure Properties and Decision properties for CFL, Deciding properties of CFL. 8
- Turing Machines: Introduction, Definition of Turing Machine, TM as language Acceptors and Transducers, Computable Languages and functions, Universal TM & Other modification, multiple tracks Turing Machine. Hierarchy of Formal languages: Recursive & recursively enumerable languages, Properties of RL and REL, Introduction of Context sensitive grammars and languages, The Chomsky Hierarchy. 8
- Tractable and Untractable Problems: P, NP, NP complete and NP hard problems, Un-decidability, examples of these problems like vertex cover problem, Hamiltonian path problem, traveling sales man problem. 8
For detailed syllabus of all other subjects of CSE (IOT), 2022-23 regulation curriculum do visit CSEIOT 4th Sem subject syllabuses for 2022-23 regulation.
For all CSE (IOT) results, visit Rajasthan Technical University cse (iot) all semester results direct link.