MCA

Type: Elective
Contact Hours: 4 hours/week
Examination Duration: 3 Hours
Mode: Lecture
External Maximum Marks: 75
External Pass Marks: 30(i.e. 40%)
Internal Maximum Marks: 25
Total Maximum Marks: 100
Total Pass Marks: 40(i.e. 40%)

Instructions to paper setter for End semester exam:
Total number of questions shall be nine. Question number one will be compulsory and will be consisting of short/objective type questions from complete syllabus. In addition to compulsory first question there shall be four units in the question paper each consisting of two questions. Student will attempt one question from each unit in addition to compulsory question. All questions will carry equal marks.

Course Objectives: The objective of this course is to provide the in-depth coverage of theoretical computer science. It provides an insight about design of all types of machines and their applications.

Course Outcomes (COs)   At the end of this course, the student will be able to:
MCA-20-25(i).1                     design various finite state machines for real life problems;
MCA-20-25(i).2                    differentiate between the applications of different kind of machines;
MCA-20-25(i).3                    solve the tractable and intractable problems using various approaches;
MCA-20-25(i).4                   understand the need and importance of Turing machines and their suitability.
                                                                                     Unit – I
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 Grammers, Minimization of FA.
                                                                                     Unit – II
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.
                                                                                     Unit – III
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
                                                                                     Unit – IV
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.
Text Books:
⦁ John C. Martin, Introduction to Languages and the Theory of Computation, McGraw Hill.
⦁ Peter Linz, An introduction to formal language & automata, Jones & Bartlett publications.
Reference Books:
⦁ Hopcroft J. E. & Ullman J. D, Formal languages and their relation to Automata, Pearson Education.
⦁ Lewis, H.R. & Papadimitrious, C. H., Elements of the theory of computation. PHI Learning.
⦁ Michael Sipser, Introduction to the Theory of Computation, Cengage Learning.