Automata Theory and Computability detail syllabus for Computer Science & Engineering (Cse), 2017 scheme is taken from VTU official website and presented for VTU students. The course code (17CS54), and for exam duration, Teaching Hr/week, Practical Hr/week, Total Marks, internal marks, theory marks, duration and credits do visit complete sem subjects post given below.
For all other cse 5th sem syllabus for be 2017 scheme vtu you can visit CSE 5th Sem syllabus for BE 2017 Scheme VTU Subjects. The detail syllabus for automata theory and computability is as follows.
Module 1
Why study the Theory of Computation, Languages and Strings: Strings, Languages. A Language Hierarchy, Computation, Finite State Machines (FSM): Deterministic FSM, Regular languages, Designing FSM, Nondeterministic FSMs, From FSMs to Operational Systems, Simulators for FSMs, Minimizing FSMs, Canonical form of Regular languages, Finite State Transducers, Bidirectional Transducers. Textbook 1: Ch 1, 2, 3, 4, 5.1 to 5.10
Module 2
For complete syllabus and results, class timetable and more pls download iStudy. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.
Module 3
Context-Free Grammars(CFG): Introduction to Rewrite Systems and Grammars, CFGs and languages, designing CFGs, simplifying CFGs, proving that a Grammar is correct, Derivation and Parse trees, Ambiguity, Normal Forms. Pushdown Automata (PDA): Definition of non-deterministic PDA, Deterministic and Non-deterministic PDAs, Non-determinism and Halting, alternative equivalent definitions of a PDA, alternatives that are not equivalent to PDA. Textbook 1: Ch 11, 12: 11.1 to 11.8, 12.1, 12.2, 12, 4, 12.5, 12.6
Module 4
Context-Free and Non-Context-Free Languages: Where do the Context-Free Languages(CFL) fit, Showing a language is context-free, Pumping theorem for CFL, Important closure properties of CFLs, Deterministic CFLs. Algorithms and Decision Procedures for CFLs: Decidable questions, Un-decidable questions. Turing Machine: Turing machine model, Representation, Language acceptability by TM, design of TM, Techniques for TM construction. Textbook 1: Ch 13: 13.1 to 13.5, Ch 14: 14.1, 14.2, Textbook 2: Ch 9.1 to 9.6
Module 5
For complete syllabus and results, class timetable and more pls download iStudy. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.
Course Outcomes:
The students should be able to:
- Tell the core concepts in automata theory and Theory of Computation
- Explain how to translate between different models of Computation (e.g., Deterministic and Non-deterministic and Software models).
- Interpret Grammars and Automata (recognizers) for different language classes and become knowledgeable about restricted models of Computation (Regular, Context Free) and their relative powers.
- Develop skills in formal reasoning and reduction of a problem to a formal model, with an emphasis on semantic precision and conciseness.
- The question paper will have TEN questions.
- There will be TWO questions from each module.
- Each question will have questions covering all the topics under a module.
- The students will have to answer FIVE full questions, selecting ONE full question from each module.
Classify a problem with respect to different models of Computation.
Question paper pattern:
Text Books:
- Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson Education, 2012/2013
- K L P Mishra, N Chandrasekaran, 3rd Edition, Theory of Computer Science, PhI, 2012.
Reference Books:
- John E Hopcroft, Rajeev Motwani, Jeffery D Ullman, Introduction to AutomataTheory, Languages, and Computation, 3rd Edition, Pearson Education, 2013
- Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning, 2013
- John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata McGraw -Hill Publishing Company Limited, 2013
- Peter Linz, An Introduction to Formal Languages and Automata, 3rd Edition, Narosa Publishers, 1998
- Basavaraj S. Anami, Karibasappa K G, Formal Languages and Automata theory, Wiley India, 2012
- C K Nagpal, Formal Languages and Automata Theory, Oxford University press, 2012.
For detail syllabus of all other subjects of BE Cse, 2017 scheme do visit Cse 5th Sem syllabus for 2017 scheme.
Dont forget to download iStudy for latest syllabus and results, class timetable and more.