Recursive & Recursively Enumerable Sets in Computation 📚

calicut 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 Linz