DFA Minimization|Theory of Computation|Toc malayalam

#bca #toc #theory_of_computation #mealymachinecalicut university bca and bsc computer science #bca #mca #msccs #btec #mtec #calicutuniversity #kannuruniversity #keralauniversity #mguniversity#Theory_of_computation#toc#calicut_university3rd_semester_bsc_computer_ science/bca#malayalam #hsst computer_science#bca #calicutuniversity #bsc_computerscience #mca #btec_cs #mtec_cs #bsc_it #msc_cs #mca #calicut_university #keralauniversity #mg_university #kerala_university #cusat #ktu #delhi_university #jamiamilia #iit #nit #kerala #rutronix#keltron#gtec#keralapsc#ssc#upsc#lbs# semester #Calicut University BSc. CS/bca 3rd_semester #Calicut University Bca /bsc computer science 3rdsemester#gate#ugcnet#nielt#collegeUniversityexams#asap#plusone_computer_science#Theory of computation| Set and Types of Sets |Malayalam BCA3C06 –Theory of Computation Contact Hours per Week: 5 Number of Credits: 3 Number of Contact Hours: 80 Hrs. Course Evaluation: Internal – 15 Marks + External – 60 Marks Objective • To get a general introduction to the theory of Computer Science • To get a general understanding on different languages, grammar and automata Prerequisites Basic knowledge in discrete structures and graph theory. Course Outline UNIT I (10T) Introduction to Mathematical preliminaries: Sets, Functions and Relations, graphs and trees, Strings and their Properties, Proof techniques: By induction, by contradiction. UNIT II (10T) Formal languages: Definitions and examples, Chomsky classification of languages, Languages and their relation, Recursive and Recursively enumerable sets, Languages and automata. UNIT III (20T) Theory of Automata: Definition of automaton, description of a finite automaton, DFA, transition systems, properties of transition functions, acceptability of a string by a finite automaton, Non deterministic finite state machines: with epsilon moves and without epsilon moves, equivalence of DFA and NDFA, Mealy and Moore Models, minimization of finite automata. Regular sets and grammar: Regular expressions, Finite automata and regular expressions, closure properties of regular sets, Algebraic laws for regular expressions, regular sets and regular grammars BCA (Academic Year 2019-20 Onwards) 44 | P a g e Board of Studies UG | Computer Science& Applications | University of Calicut Page 45 of 137 UNIT IV (20T) Context free languages: Context free languages and derivation trees, Ambiguity in context free grammars, Simplification of context free languages, normal forms for context free languages. UNIT V (20T) Pushdown automata: Definition, Acceptance by PDA, Pushdown automata and Context-free languages, Parsing and Pushdown Automata. Turing Machines: Turing machine model, representation of Turing machines, languages accepted by Turing machine. Textbooks 1. Theory of Computer Science- Automata, Languages and Computation- K.L.P. Mishra, N Chandrasekaran, PHI 2. Theory of Computation, Sachin Agrawal, Vikas Publishing House Reference books 1. Introduction to Automata Theory, Languages & Computations, J.E Hopcroft, R Motwani & J. D. Ullman 2. Elements of theory of Computation, Second edition, H.R. Lewis and C.H. Papadimitriou, Pearson education. 3. An Introduction to the Theory of Computer Science, Languages and Machines-Thomas A. Sudkamp, Third Edition, Pearson Education. 4. An Introduction to Formal languages and Automata- Peter LinzConversion of Moore machine to Mealy machine|Theory of Computation|Toc malayalam