Theory of Computation syllabus

2019 PATTERN. This is the 2019 pattern syllabus, the latest SPPU has published on its site for Third Year Information Technology. A 2024 pattern syllabus for this year has not been published there yet, so confirm with your college which pattern applies to you.

314441 · Third Year Information Technology, SPPU 2019 pattern. Every unit, the marks scheme, course outcomes and books, copied from the official syllabus PDF.

3144413 h/week theoryMid-Sem 30 + End-sem 70

06.units

03.credits

Unit-wise syllabus

UNIT I

Finite Automata

6 hours

Basic Concepts: Symbols, Strings, Language, Formal Language. Finite Automata (FA): Formal definition and notations for FSM, Concept of state transition diagram and transition table for FA, Construction of DFA, NFA, NFA with epsilon moves. Conversion of NFA with epsilon moves to NFA, Conversion of NFA to DFA, and Conversion of NFA with epsilon moves to DFA, Minimization of FA, Equivalence of FAs, and Applications of FA. Finite State Machine with output: Moore and Mealy machines - Definition, Construction, Inter- Conversion.

UNIT II

Regular Expressions and Languages

6 hours

Regular Expressions (RE) : Definition and Identities of RE, Operators of RE, Equivalence of two regular expressions, Equivalence of regular expressions and regular languages (RL), Conversion of RE to FA using direct method, Conversion of FA to RE using Arden’s theorem, Pumping lemma for RLs, Closure properties of RLs, Applications of Regular Expressions. TE (Information Technology) Syllabus (2019 Course) 9 Curriculum for Third Year of Information Technology (2019 Course), Savitribai Phule Pune University

UNIT III

Context Free Grammar and Language

6 hours

Grammar: Introduction and representation, Chomsky Hierarchy, Formal definition of Regular Grammar(RG), Conversions: LRG to RLG, RLG to LRG, RG to FA, FA to RG. Context Free Grammar (CFG): Definition of CFG, Derivation tree, sentential forms, Leftmost and Rightmost derivations, Ambiguous Grammar and unambiguous grammar, Context Free Language (CFL). Grammar Simplification, Normal forms: Chomsky Normal Form, Greibach Normal Form. Closure properties of CFL, Pumping lemma for CFL.

UNIT IV

Pushdown Automata and Post Machine

6 hours

Pushdown Automata(PDA) : Introduction and formal definition of PDA, Construction of Transition diagram and Transition table for PDA, Instantaneous Description of PDA, Equivalence of Acceptance by Final State & Empty stack, Deterministic PDA and Nondeterministic PDA, Context Free Language and PDA Conversion of CFG to PDA and PDA to CFG. Post Machine (PM): Definition and construction of Post Machine.

UNIT V

Turing Machine

6 hours

Turing Machine (TM) : Formal definition of a Turing machine, Design of Turing machines, Variants of Turing Machines: Deterministic TM, Nondeterministic TM, Multi-tape TM, Universal Turing Machine, Halting problem of TM , Church-Turing thesis, Recursive Languages and Recursively Enumerable Languages, Post Correspondence Problem.

UNIT VI

Computational Complexity

6 hours

Decidability: Decidable problems concerning regular languages, Decidable problems concerning context free languages, Un-decidability. Computational Complexity: Measuring Complexity, The Class P, Examples of problems in P, The Class NP, and Examples of problems in NP, Reducibility, Mapping Reducibility, Polynomial Time Reduction and NP Completeness. Satisfiability Problem, NP Completeness of the SAT Problem, Normal Forms for Boolean Expressions, Cook’s theorem, Node-C over Problem. TE (Information Technology) Syllabus (2019 Course) 10 Curriculum for Third Year of Information Technology (2019 Course), Savitribai Phule Pune University

Marks and credits

Head	Marks	Credit
Mid-Sem (mid-semester exam)	30	3
End-semester exam	70	3

Prerequisite: 1. Discrete Structures. 2. Data structures..

Course outcomes

CO1Construct finite automata and its variants to solve computing problems.
CO2Write regular expressions for the regular languages and finite automata.
CO3Identify types of grammar, design and simplify Context Free Grammar.
CO4Construct Pushdown Automata machine for the Context Free Language.
CO5Design and analyze Turing machines for formal languages.
CO6Understand decidable and undecidable problems, analyze complexity classes.

Books

Text books

John C. Martin, Introduction to Language and Theory of Computation, TMH, 3rd Edition, ISBN: 978-0070660489.
Vivek Kulkarni, Theory of Computation, Oxford University Press,ISBN- 13 : 978-0198084587.

Reference books

John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, Introduction to Automata Theory Languages and Computation, Addison-Wesley, ISBN 0-201-44124-1.
K.L.P Mishra, N. Chandrasekaran, Theory of Computer Science : Automata, Languages and Computation, Prentice Hall India, 2nd Edition.
Michael Sipser, Introduction to the Theory of Computation, CENGAGE Learning, 3rd Edition ISBN- 13:978-81-315-2529-6.
Daniel Cohen, “Introduction to Computer Theory”, Wiley & Sons, ISBN 97881265133454.
Kavi Mahesh, “Theory of Computation: A Problem-Solving Approach”, Wiley India, ISBN-1081265331106. E- Books / E- Learning References :

FAQ

How many units are in Theory of Computation?

Theory of Computation (314441) has 6 units: Unit I Finite Automata (6 h); Unit II Regular Expressions and Languages (6 h); Unit III Context Free Grammar and Language (6 h); Unit IV Pushdown Automata and Post Machine (6 h); Unit V Turing Machine (6 h); Unit VI Computational Complexity (6 h).

What is the marks scheme for Theory of Computation?

The official Information Technology 2019 pattern syllabus lists mid-semester (Mid-Sem) for 30 marks and the end-semester exam for 70 marks, for 3 credits.

What should I know before Theory of Computation?

Prerequisite listed in the syllabus: 1. Discrete Structures. 2. Data structures..