Syllabus
|
Course Code: MCA-20-25 Course Name: Elective-II - (i) Theory of Computation |
||
| MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
|---|---|---|
| 1 | Finite State Machines: Finite Automata, Designing of DFA and NDFA, NFA with E-Transitions, Equivalence of DFA and NFA with proof, Regular Expressions and Regular languages, Laws of Regular Expressions, Kleene’s Theorem 1 and 2, Properties and Limitations of FSM FSM with Output: Moore and Mealy Machines, Arden’s Theorem with proof, Closure Properties of Regular Sets, Pumping Lemma for Regular Grammars, Minimization of FA. |
|
| 2 | Formal Grammars: Definition, Construction of Regular & Context Free Grammar, Derivation, Parse Trees, Ambiguity, Removal of Ambiguity, Simplification of Context Free Grammar, CNF and GNF, Closure properties of CFL, Pumping Lemma for CFL. Pushdown Automaton: Introduction, Types of PDA, Designing of PDA’s, Conversion from PDA to CFG and vice-versa. |
|
| 3 | Linear Bounded Automata (LBA), Turing Machines (TM), General Model of Computation, TM as Language Acceptors, TM as Computing Partial Functions, Combining TM, Multi-Tape TM, Restricted and Universal TM; TM and Computers. Recursive and recursively-enumerable languages and Properties, More General Grammars |
|
| 4 | Reductions and the Halting Problem, Post’s correspondence problem, Rice's theorem, Cook’s Theorem, decidability of membership, emptiness and equivalence problems of languages, Decidable languages and problems, Diagonalization method. Computable Functions: Primitive recursive functions, Godel Numbering, Tractable and Intractable problems, Computable Complexity. |
|
