CSC504: Theory of Computer Science Syllabus for CS 5th Sem 2018 Pattern Mumbai University

Theory of Computer Science detailed syllabus scheme for Computer Engineering (CS), 2018 regulation has been taken from the University of Mumbai official website and presented for the Bachelor of Engineering students. For Course Code, Course Title, Test 1, Test 2, Avg, End Sem Exam, Team Work, Practical, Oral, Total, and other information, do visit full semester subjects post given below.

For all other Mumbai University Computer Engineering 5th Sem Syllabus 2018 Pattern, do visit CS 5th Sem 2018 Pattern Scheme. The detailed syllabus scheme for theory of computer science is as follows.

Theory of Computer Science Syllabus for Computer Engineering TE 5th Sem 2018 Pattern Mumbai University

Course 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 pdf platform to make students’s lives easier.
.

Course Outcomes:

On successful completion of course learner will be able to:

1. Identify the central concepts in theory of computation and differentiate between deterministic and nondeterministic automata, also obtain equivalence of NFA and DFA.
2. Infer the equivalence of languages described by finite automata and regular expressions.
3. Devise regular, context free grammars while recognizing the strings and tokens.
4. Design pushdown automata to recognize the language.
5. Develop an understanding of computation through Turing Machine.
6. Acquire fundamental understanding of decidability and undecidability.

Prerequisites:

Discrete Mathematics

Module 1

Basic Concepts and Finite Automata 09 03

1. 1. Alphabets, Strings, Languages, Closure properties.
   2. Finite Automata (FA) and Finite State machine (FSM).
2. 1. Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA): Definitions, transition diagrams and Language recognizers
   2. NFA to DFA Conversion
   3. Equivalence between NFA with and without a- transitions
   4. Minimization of DFA
   5. FSM with output: Moore and Mealy machines, Equivalence
   6. Applications and limitations of FA

Module 2

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 pdf platform to make students’s lives easier.
.

Module 3

Grammars 08 03

1. 1. Grammars and Chomsky hierarchy
2. 1. Regular Grammar (RG.
   2. Equivalence of Left and Right linear grammar
   3. Equivalence of RG and FA
3. Context Free Grammars (CFG)
   1. Definition, Sentential forms, Leftmost and Rightmost derivations, Parse tree, Ambiguity.
   2. Simplification and Applications.
   3. Normal Forms: Chomsky Normal Forms (CNF) and Greibach Normal Forms (GNF).
   4. CFLs – Pumping lemma, Closure properties

Module 4

Pushdown Automata(PDA. 04 01

1. Definition, Transitions ,Language of PDA
2. Language acceptance by final state and empty stack
3. PDA as generator, decider and acceptor of CFG.
4. Deterministic PDA , Non-Deterministic PDA
5. Application of PDA.

Module 5

Turing Machine (TM. 09 03

1. Definition, Transitions
2. Design of TM as generator, decider and acceptor.
3. Variants of TM: Multitrack, Multitape
4. Universal TM.
5. Equivalence of Single and Multi Tape TMs.
6. Applications, Power and Limitations of TMs.
7. Context Sensitivity and Linear Bound Automata.

Module 6

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 pdf platform to make students’s lives easier.
.

Assessment

Internal Assessment: Assessment consists of two class tests of 20 marks each. The first class test is to be conducted when approx. 40% syllabus is completed and second class test when additional 40% syllabus is completed. Duration of each test shall be one hour. End Semester Theory Examination:

1. Question paper will comprise of 6 questions, each carrying 20 marks.
2. The students need to solve total 4 questions.
3. Question No.1 will be compulsory and based on entire syllabus.
4. Remaining question (Q.2 to Q.6) will be selected from all the modules.

Text Books:

1. John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman, Introduction to Automata Theory, Languages andComputation, Pearson Education.
2. Michael Sipser, Theory of Computation, Cengage learning.
3. Vivek Kulkarni, Theory of Computation, Oxford University Press, India.

Reference Books:

1. J. C. Martin, Introduction to Languages and the Theory of Computation, Tata McGraw Hill.
2. Kavi Mahesh, Theory of Computation: A Problem Solving Approach, Wiley-India.

For detail syllabus of all other subjects of Computer Engineering (CS) 5th Sem 2018 regulation, visit CS 5th Sem Subjects syllabus for 2018 regulation.