Theory of Computation

Download Theory Of Computation

310245: THEORY OF COMPUTATION
Examination Scheme Theory: 100 Marks
Teaching Scheme Lectures: 3 Hrs/Week

Objectives:
• Study abstract computing models
• Learn about the theory of computability and complexity.
Prerequisites:
• Discrete Structures
• Data Structures and Algorithms

Unit I (6 Mrs)
Automata Theory: Introduction to Finite Automata, Structural Representations, Automata
and Complexity, Central Concepts to Automata Theory: Alphabets, Strings, Languages and
Problems, Finite Automata: An Informal Picture of FA, Deterministic Finite Automaton
(DFA): How a DFA processes Strings, Simpler Notations for DFA, Extending the transition
function to strings, the language of DFA, Non-deterministic Finite Automaton (NFA): NFA,
Extended transition function, the language of an NFA, Equivalence of NFA and DFA, FA
with e-transitions: Use of e-transitions, NFA with e, e-closures, Extended transitions and
languages for e-NFA, Eliminating €-transitions-Con version of NFA with e to NFA without
e, Conversion of NFA without e to DFA, Conversion of NFA with 6 to DFA (direct method),
FA with output: Moore and Mealy machines -Definition, models, inter-conversion.

Unit II (6 Hrs)
Regular Expressions (RE) and Languages: Regular Expressions - Operators of RE,
Building RE, Precedence of operators, Algebraic laws for RE, Arden's Theorem, FA and RE:
DFA to RE, RE to DFA (RE to s-NFA & e-NFA to DFA and RE to DFA-direct method), FA
limitations, Properties of Regular Languages: pumping lemma for regular languages, closure
and decision properties of regular languages, Equivalence and minimization of automata,
Application of RE: Regular expressions in Unix, GREP utilities of Unix, Lexical analysis and
finding patterns in text.

Unit III (6 Hrs)
Context Free Grammars (CFG) and Languages: Context Free Grammar- Definition,
derivations, languages of a grammar, sentential form, Parse Tree- inference, derivation and
parse tree, from inference to tree, Ambiguity in grammars and languages: removal of
ambiguity, inherent ambiguity, Properties of CFL- Normal forms- Chomsky Normal Form
and Greibach Normal Form, Eliminating unit productions, useless production, useless
symbols, and e-productions, Regular Grammar - definition, left linear and right linear
Regular Grammar, Regular Grammar and Finite Automata, FA to RG and RG to FA, Interconversion
between left linear and right linear regular grammar.

Unit IV (6 Hrs)
Push Down Automata (PDA): Definition, The Language of PDA, Equivalence of PDA's
and CFG- CFG to PDA, PDA to CFG, Deterministic Push Down Automata (DPDA)-
Regular language and DPDA, DPDA and CFL, DPDA and ambiguous grammar, Nondeterministic
Push Down Automata (NPDA), The pumping lemma for CFL, Closure
properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Application of CFG:
Parser, Markup languages, XML and Document Type Definitions.
Unit V (6 Hrs) Turing Machine: Problems that computers cannot solve, The Turing
Machine(TM)-Notation, the language of TM, TM and Halting, Programming techniques to TM,
Extensions to basic TM, TM and Computers. Introduction to Post Machines, Comparison
between FA, PDA, Post Machine and TM

Unit VI (6 Hrs)
Introduction to Computational Complexity: Un-decidability: A Language that is not
recursively enumerable, An un-decidable problem that is RE, Post Correspondence Problem,
Intractable Problems* The classes P and NP, Problems solvable in polynomial time, Nondeterministic
Polynomial time, Polynomial time reduction and NP-complete problems.

Text Books:
1. Hopcroft J., Mptwani R., Ullman J., "Introduction to Automata Theory, Languages and
Computations", Second edition, Pearson Education Asia, ISBN 81-7808-347-7
2. Martin J., "Introduction to Language and Theory of Computation", Third edition, Tata
McGraw-Hill, ISBN 0-07-049939-X

Reference Books:
1. Lewis H., Papadimitriou C., "Elements of Theory of Computation", Second edition, Pearson
[education Asia, ISBN 81-7808-487-2
2. Cohen D., "Introduction to Computer Theory", Wiley Publications, edition, ISBN-9971-51-
220-3
3. Moret B., " The Theory of Computation", Pearson Education Asia, ISBN 81-7808-487-2
4. Mishra K., Chandrasekaran N., 'Theory of Computer Science (Automata, Languages and
Computation)", Second Edition, Prentice Hall of India, ISBN-81-2030-1271-6.