BCA601T : THEORY OF COMPUTATION

Total Teaching Hours : 60 No of Hours / Week : 04

Unit – I

Introduction to Finite Automata: The central concepts of Automata theory; Deterministic

finite automata; Nondeterministic finite automata. An application of finite automata,

Page 33 of 38

Finite automata with Epsilon transitions.

[ 12 Hours ]

Unit – II

Regular Expressions: Finite Automata and Regular Expressions Applications of Regular

Expressions. Regular languages; Proving languages not to be regular languages; Closure

properties of regular languages; Decision properties of regular languages; Equivalence

and minimization of automata.

[ 12 Hours ]

Unit – III

Context–free grammars: Parse trees; Applications; Ambiguity in grammars and

Languages. Definition of the Pushdown automata; the languages of a PDA; Equivalence

of PDA’s and CFG’s.

[ 12 Hours ]

Unit – IV

Deterministic Pushdown Automata:Normal forms for CFGs; The pumping lemma for

CFGs; Closure properties of CFLs. Problems that Computers cannot solve.

[ 12 Hours ]

Unit – V

The Turing machine:Programming techniques for Turing Machines. Undecidability, A

Language that is not recursively enumerable; An Undecidable problem that is RE; Post’s

Correspondence problem.

[ 12 Hours ]

Text Book:

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

Theory, Languages and Computation, 3rd Edition, Pearson Education, 2011.

Reference Books:

1. John C Martin: Introduction to Languages and Automata Theory, 3rd Edition,

Tata McGraw-Hill, 2007.

2. Daniel I.A. Cohen: Introduction to Computer Theory, 2nd Edition, John Wiley &

Sons, 2009.

3. Thomas A. Sudkamp: An Introduction to the Theory of Computer Science,

Languages and Machines, 3rd Edition,Pearson Education, 2006

### Bangalore North University BCA 5th Sem Previous year question paper and Study Materials

Bangalore University BCA 5th sem Study Material, Previous Year Question Paper, Solved Question Paper, Notes Are Available Free Download

### Bangalore North University BCA 3rd Sem Previous year question paper and Study Materials

Bangalore University BCA 3rd sem Study Material, Previous Year Question Paper, Solved Question Paper, Notes Are Available Free Download

### Bangalore North University BCA 1st Sem Study Materials

bangalore university bca 1st sem previous year question papers