THEORY OF COMPUTATION (BCS503)

THEORY OF COMPUTATION

Course Code BCS503 
CIE Marks 50
Teaching Hours/Week (L: T:P: S) (3:2:0:0) 
SEE Marks 50
Total Hours of Pedagogy 50 
Total Marks 100
Credits 04 
Exam Hours 3
Examination type (SEE) Theory

Module-1 

Introduction to Finite Automata, Structural Representations, Automata and Complexity. The Central

Concepts of Automata Theory. Deterministic Finite Automata, Nondeterministic Finite Automata, An

Application: Text Search, Finite Automata with Epsilon-Transitions.

Module-2 

Regular Expressions, Finite Automata and Regular Expressions, Proving Languages not to be Regular.

Closure Properties of Regular Languages, Equivalence and Minimization of Automata, Applications of

Regular Expressions

Module-3 

Context-Free Grammars, Parse Trees, Ambiguity in Grammars and Languages, Ambiguity in

Grammars and Languages, Definition of the Pushdown Automaton, The Languages of a PDA,

Equivalence of PDA's and CFG's, Deterministic Pushdown Automata.

Module-4 

Normal Forms for Context-Free Grammars, The Pumping Lemma for Context-Free Languages, Closure

Properties of Context-Free Languages.

Module-5 

Introduction to Turing Machines: Problems That Computers Cannot Solve, The Turing Machine,

Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine, Undecidability: A

Language That Is Not Recursively Enumerable.

Suggested Learning Resources:

Books

1. John E Hopcroft, Rajeev Motwani, Jeffrey D. Ullman,” Introduction to Automata Theory,

Languages and Computation”, Second Edition, Pearson.

Reference:

1. Elain Rich, “Automata,Computability and complexity”, 1st Edition, Pearson Education,2018.

2. K.L.P Mishra, N Chandrashekaran , 3rd Edition , ‘Theory of Computer Science”,PHI,2012.

3. Peter Linz, “An introduction to Formal Languages and Automata “, 3rd Edition, Narosa

Publishers,1998.

4. Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning,2013.

5. John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata

McGraw –Hill Publishing Company Limited, 2013.