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

Important Links:

1. Problems Handwritten Notes Module-1 to Module-5 [Click here to download]

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.

Click here to download Module-1

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

Click here to download Module-2

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.

Click here to download Module-3

Module-4 

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

Properties of Context-Free Languages.

Click here to download Module-4

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.

Click here to download Module-5 

Important Links:

1. Problems Handwritten Notes Module-1 to Module-5 [Click here to download]

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.