Department of Computer Science and Engineering

B.Tech. II (CO) Semester - 4

L

T

P

C

CO202 : THEORETICAL COMPUTER SCIENCE (CS-I)

3

1

0

4
COURSE OBJECTIVES
  • Introduce students to the concepts of Theory of computation in computer science.
  • Introduce students to the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability.
  • Enhance/Develop students' ability to understand and conduct mathematical proofs for computation and algorithms.
COURSE OUTCOMES
After successful completion of this course, student will be able to
  • Understand formal language theory and its application to computer science
  • Apply mathematical preliminaries to develop the basic components of language design
  • Design simple computational machines using the concepts of language theory
  • Correlate computability with formal computational machines
COURSE CONTENT
Introduction

(02 Hours)

Basic Mathematical Objects: Sets, Logic, Functions, Relations, Strings, Alphabets, Languages; Mathematical Induction: Inductive proofs, Principles; Recursive Definitions; Set Notation.

Finite Automata and Regular Expressions

(12 Hours)

Finite State systems, Regular Languages & Regular Expressions, Deterministic Finite Automata; Nondeterministic Finite Automata, Kleene’ Theorem; Two-way Finite Automata, Finite Automata with output, Properties of Regular Sets: The Pumping Lemma for Regular sets, Closure properties, Decision properties of regular languages, Equivalence and minimization of Automata.
Context Free Grammars

(14 Hours)

Definition, Derivation trees & Ambiguity, Inherent ambiguity, Parse tree, Application of  CFG, Simplification of CFG, Normal form of CFG,  Chomsky Normal form and Chomsky Hierarchy,  Unrestricted grammars, Context-sensitive languages, Relations between classes of languages, Properties of Context Free Languages: The Pumping Lemma, Closure properties, Decision properties of CFL.
Pushdown Automata

(04 Hours)

Definitions, Languages of  PDA, Equivalence of PDA and CFG , Deterministic PDA
Turing Machines

(06 Hours)

Turing Machine Model, Language of a Turing Machine, Programming techniques of the TM,  Variations of TM (Multiple TM, One-tape and Multi-tape TM etc), Deterministic and Non deterministic TM, Universal TM, Churche thesis, Recursively Enumerable Languages.
Computational Complexity

(04 Hours)

Time and Space Complexity, Growth Rate, Complexity classes, Tractable and Non tractable Problems: P and NP, Cooks’s theorem.
Tutorials will be based on the coverage of the above topics separately

(14 Hours)
(Total Contact Time: 42 Hours + 14 Hours = 56 Hours)
BOOKS RECOMMENDED
  1. 1. John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: “Introduction to Automata theory, languages computation, 3/E, Pearson India, 2008
  2. John C Martin : “Introduction to Languages & the Theory of Computation”, 3/E, Tata McGraw-Hill, 2011
  3. Daniel I A Cohen : “Introduction to Computer Theory”, John Wiley & Sons, 2/E, Reprint 2008
  4. A.M. Natarajan, A.Tamilarasi: “Theory of computation”, New Age Publication, 1/E, 2003.
  5. Sushil Kumar Azad : “Theory of Computation, An introduction to /automata, Formal Languages And Computability”, Dhanpat Ray & Co., New Delhi, 2005.
  6. Andrew Ilachinski, “Cellular Automata”, World Scientific, 2001
  7. Michael Sipser: “Introduction to the Theory of Computation”,Cengage Learning, 3/E, 2013