18CS54: Automata Theory and Computability IS Syllabus for BE 5th Sem 2018 Scheme VTU

Automata Theory and Computability detailed Syllabus for Information Science Engineering (IS), 2018 scheme has been taken from the VTUs official website and presented for the VTU students. For Course Code, Subject Names, Teaching Department, Paper Setting Board, Theory Lectures, Tutorial, Practical/Drawing, Duration in Hours, CIE Marks, Total Marks, Credits and other information do visit full semester subjects post given below. The Syllabus PDF files can also be downloaded from the official website of the university.

For all other VTU IS 5th Sem Syllabus for BE 2018 Scheme, do visit VTU IS 5th Sem Syllabus for BE 2018 Scheme Subjects. The detailed Syllabus for automata theory and computability is as follows.

Course Learning Objectives:

For the complete Syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.

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 RBT: L1, L2

Module 2

Regular Expressions (RE): what is a RE?, Kleene’s theorem, Applications of REs, Manipulating and Simplifying REs. Regular Grammars: Definition, Regular Grammars and Regular languages. Regular Languages (RL) and Non-regular Languages: How many RLs, To show that a language is regular, Closure properties of RLs, to show some languages are not RLs. Textbook 1: Ch 6, 7, 8: 6.1 to 6.4, 7.1, 7.2, 8.1 to 8.4 RBT: L1, L2, L3

Module 3

Module 4

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. Variants of Turing Machines (TM), The model of Linear Bounded automata. Textbook 1: Ch 14: 14.1, 14.2, Textbook 2: Ch 9.1 to 9.8 RBT: L1, L2, L3

Module 5

Decidability: Definition of an algorithm, decidability, decidable languages, Undecidable languages, halting problem of TM, Post correspondence problem. Complexity: Growth rate of functions, the classes of P and NP, Quantum Computation: quantum computers, Church Turing thesis. Applications: G.1 Defining syntax of programming language, Appendix J: Security Textbook 2: 10.1 to 10.7, 12.1, 12.2, 12.8, 12.8.1, 12.8.2 Textbook 1: Appendix: G.1(only), J.1 & J.2 RBT: L1, L2, L3

Course Outcomes:

Question Paper Pattern:

The question paper will have ten questions.
Each full Question consisting of 20 marks
There will be 2 full questions (with a maximum of four sub questions) from each module.
Each full question will have sub questions covering all the topics under a module.
The students will have to answer 5 full questions, selecting one full question from each module.

Textbooks:

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:

For detail Syllabus of all other subjects of BE 5th Sem Information Science Engineering, visit (IS) 5th Sem Syllabus Subjects.

For all (CBSE & Non-CBSC) BE results, visit VTU BE all semester results direct links.

InI KA