BAIC — Calicut University B.C.A Honours Programme Scheme and Syllabus | BAIC

Detailed Syllabus Page 160 of 241 limitations of computation through the study of the halting problem and other undecidable problems. Instructor-created exams / Quiz CO6 Solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation E P Practical Assignment / Instructor-created exams / Quiz * - Remember (R), Understand (U), Apply (Ap), Analyse (An), Evaluate (E), Create (C) # - Factual Knowledge(F) Conceptual Knowledge (C) Procedural Knowledge (P) Metacognitive Knowledge (M) Module Unit Content Hrs (48+12) Mark I FINITE AUTOMATA 10 16 1 Formal Language:

Definition, Chomsky classification of Grammar, Language and Relation, Language and Automata 2 2 Finite Automata: DFA, NFA with and without €- moves 2 3 Equivalence of DFA and NFA 2 4 Equivalence of NFA and €-NFA 2 5 Mealy and Moore Models - Conversions 2 II REGULAR LANGUAGE, REGULAR EXPRESSION 10 18 6 Regular Languages:

Regular Expressions, Ardens Theorm 2 7 Conversion of Regular Expression to Finite Automata 2 8 Closure properties of RLs 2 9 Pumping lemma for RLs 2 10 Myhill-Nerode theorem 2 III PUSH DOWN AUTOMATA, CONTEXT FREE LANGUAGE 14 18 11 Pushdown Automata - Instantaneous Description - Transition Diagram 3 12 Deterministic and Non Deterministic PDA 3 13 Equivalence of PDAs and CFGs, Pumping lemma for CFLs 2 14 Closure properties of CFLs, Simplification of CFLs 2 15 Chomsky Normal form (CNF) and Greibach Normal form (GNF) 2 16 CYK algorithm for CFL membership 2 IV TURING MACHINE, UNDECIDABILITY 14 18 17 Turing Machine - Instantaneous Description - Transition Diagram 3 18 Variants of TMs - Equivalence of the various variants with basic model 3 19 Recursively Enumerable and Recursive languages 2 20 Church Turing hypothesis - Rices theorem 2 21 Undecidability of Posts correspondence problem 2 22 The Class P and NP 2 V Open Ended Module- Application Level 12 1.

Application of regular expressions in pattern matching and text processing. 2. Analysis of context-free languages using pumping lemma