All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

University of Mumbai Branch: Computer Semester: V Engineering Subject: Theory of Computer Science (Abbreviated as TCS) Periods per Week Lecture 04 (each 60 min) Practical 02 Tutorial -Hours Evaluation System Theory 03 Practical and Oral -Oral --Term Work --Total 03 Class: T.E.
Marks 100 --25 125
OBJECTIVES
Objectives of the Course: This course aims to build concepts regarding the fundamental principles of Grammars, Automata Theory, Turing Machines, Push Down Automata, Undecidability and Intra

Tags

Transcript

University of MumbaiClass:
T.E.
Branch:
ComputerEngineering
Semester:
V
Subject:
Theory of Computer Science (Abbreviated as
TCS
)
Lecture04Practical02Periods per Week(each 60 min)Tutorial--Hours MarksTheory03 100Practical and Oral -- --Oral--- --Term Work--- 25Evaluation SystemTotal03 125
OBJECTIVES
Objectives of the Course
: This course aims to build concepts regarding thefundamental principles of Grammars, Automata Theory, Turing Machines, PushDown Automata, Undecidability and Intractable Problems
PREREQUISITES
Prerequisites:
Discrete Structures and Graphs Theory (e.g. Graphs, Trees,Logic and Proof Techniques) and also familiar with common Data Structures,Recursion, and the role of major system components such as Compilers.
Module Contents Hours
1 Introduction:alphabets, Strings and Languages, automata andGrammars. Finite. Automata (FA) -its behavior; DFA -Formaldefinition, simplified notations (state transition diagram,transition table), Language of a DFA. NFA -Formaldefinition, Language of an NFA. An Application: Text Search,FA with epsilon-transitions, Eliminating epsilon-transitions,Equivalence of DFAs and NFAs.052 Regular expressions (RE) -Definition, FA and RE, RE to FA,FA to RE, algebraic laws for RE, applications of REs,Regular grammars and FA, FA for regular grammar, Regulargrammar for FA033 Proving languages to be non-regular - Pumping Lenma,and its applications. Some closure properties of Regularlanguages -Closure under Boolean operations, reversal,homomorphism, inverse homomorphism, etc. M hill-NerodeTheorem.034 DFA Minimization
.
Some decision properties of Regular languages -emptiness,finiteness, membership, equivalence of two DF As or REs,Finite automata with output.03
5 Context-free Grammars (CFGs) -Formal definition, sententialforms, leftmost and rightmost derivations, the language of aCFG. Derivation tree or Parsetree-Definition, Relationship between parse trees andderivations. Parsing and ambiguity, Application of CFGs,Ambiguity in grammars and Languages. Simplification ofCFGs -Removing useless symbols, epsilon-Productions, andunit productions, Normal forms -CNF and GNF. Proving thatsome languages are not context free -Pumping lemma forCFLs, applications. Some closure properties of CFLs -Closureunder union, concatenation, Kleene closure, substitution,Inverse homomorphism, reversal, intersection with regular set,etc. Some more decision properties of CFLs, Review of someundecidable CFL problems.106 Pushdown Automata (PDA) -Formal definition, behavior andgraphical notation, Instantaneous descriptions (Ids), Thelanguage of PDA (acceptance by final state and empty stack).Equivalence of acceptance by final state and empty stack,Equivalence of PDAs and CFGs, CFG to PDA, PDA to CFG.DPDAs -Definition, DPDAs and Regular Languages, DPDAs,Multistack DPDAs & NPDAs and CFLs.Languages of DPDAs, NPDAs, and ambiguous grammars067 Turing Machines TM -Formal definition and behavior,Transition diagrams, Language of a TM, TM as acceptersdeciders and generators. TM as a computer of integerfunctions, Design of TMs, Programming techniques for TMs -Storage in state, multiple tracks, subroutines, etc. UniversalTMs, Variants of TMs -Multitape TMs, Nondeterministic TMs.TMs with semi-infinite tapes, Multistack machines, SimulatingTM by computer, Simulating a Computer by a TM,Equivalence of the various variants with the basic model.Recursive and recursively enumerable languages, Propertiesof recursive and recursively enumerable languages, Alanguage that is not recursively enumerable (thediagonalization language). The universal language,Undecidability of the universal language, The Halting problem,Rice’s Theorem, Greibach Theorem, Post's CorrespondenceProblem (PCP) -Definition, Undecidability of PCP.Context sensitive language and linear bounded automata.Chomsky hierarchy.108 Intractable Problems :The classes P and NP, An NP-completeproblem, A Restricted Satisfiability problem, Additional NP-complete problems, Complements of languages in NP,08
Problems Solvable in polynomial space, A problem that iscomplete for PS, Language Classes based on randomization,The complexity of primality testing.
TEXT BOOKS
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, “ Introduction toAutomataTheory, Languages and Computation”, Pearson Education.2. J.C.Martin, “Introduction to languages and the Theory of Computation”, TMH.3. Michael Sipser, “Theory of Computation”,Cengage Learning.
REFERENCES
1. O.G.Kakde, “Theory of Computation”, LP.2. Krishnamurthy E.V. , “Introductory Theory of Computer Science”, East-West press.
TERM WORK
1. Term Work should consists of at least 04 experiments and 08 assignments (atleast one implementation on each machine and at least one assignment on eachmodule).2. A Term Work should consists of Term Test must be conducted with aweightage of 10 marks.

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x