About Subject

Pattern / Course	2015 Course
Year & Branch	TE (Information Technology)
Semester I/II	II
Course code	C301(314441)
Course title	Theory of Computation
Teaching Scheme (Lect / Tut /  Pract)	Lectures: 4 Hrs/ Week
Examination Scheme	In semester Assessment: 30 End Semester Assessment : 70 Total marks: 100

Course Objectives

1	To understand problem classification and problem solving by machines.
2	To understand the basics of automata theory and its operations.
3	To study computing machines by describing, classifying and comparing different types of computational models.
4	Encourage students to study theory of computability and complexity.
5	To understand the P and NP class problems and its classification.
6	To understand the fundamentals of problem decidability and reducibility.

Course Outcomes

CO1	To construct finite state machines to solve problems in computing
CO2	To write mathematical expressions for the formal languages
CO3	To apply well defined rules for syntax verification
CO4	To construct and analyze Push Down Automata and Post Machine for formal languages
CO5	To construct and analyze Turing Machine for formal languages.
CO6	To express the understanding of computational complexity, decidability and undecidability problems

Syllabus

Unit	Content	Hrs
I	FINITE STATE MACHINES	8
	Brute Force method: Introduction to Brute Force method & Exhaustive search, Brute Force solution to 8 queens’ problem. Proof Techniques: Minimum 2 examples of each: Contradiction, Mathematical Induction, Direct proofs, Proof by counterexample, Proof by contraposition. Analysis of Algorithm: Efficiency- Analysis framework, asymptotic notations – big O, theta and omega. Amortized Analysis: Aggregate, Accounting & Potential method with the example of stack operations. Analysis of Non-recursive and recursive algorithms: Solving Recurrence Equations (Homogeneous and nonhomogeneous)..
II	REGULAR EXPRESSIONS	8
	Definition and Identities of Regular Expressions, Construction of Regular Expression of the given L, Construction of Language from the RE, Construction of FA from the given RE using direct method, Conversion of FA to RE using Arden’s Theorem, Pumping Lemma for RL, Closure properties of RLs, Applications of Regular Expressions.
III	CONTEXT FREE GRAMMAR AND LANGUAGES	8
	Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, derivation trees, Context Free Languages, Ambiguous CFG, Removal of ambiguity, Simplification of CFG, Normal Forms, Chomsky Hierarchy, Regular grammar, equivalence of RG(LRG and RLG) and FA.
IV	PUSHDOWN AUTOMATA AND POST MACHINES	8
	Push Down Automata: Introduction and Definition of PDA, Construction (Pictorial/ Transition diagram) of PDA, Instantaneous Description and ACCEPTANCE of CFL by empty stack and final state, Deterministic PDA Vs Nondeterministic PDA, Closure properties of CFLs, pumping lemma for CFL. Post Machine– Definition and construction.
V	TURING MACHINES	8
	Formal definition of a Turing machine, Recursive Languages and Recursively Enumerable Languages, Design of Turing machines, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing Machine, Nondeterministic Turing machines. Comparisons of all automata.
VI	COMPUTATIONAL COMPLEXITY	8
	Decidability: Decidable problems concerning regular languages, Decidable problems concerning context-free languages, Un-decidability, Halting Problem of TM, A Turing-unrecognizable language. Reducibility: Un-decidable Problems from Language Theory, A Simple Un-decidable Problem PCP, Mapping Reducibility. Time Complexity: Measuring Complexity, The Class P, Examples of problems in P, The Class NP, Examples of problems in NP, NP-completeness.