2CSE601: Theory of Computation

Learning Outcomes: 
After learning the course the students should be able to
Understand the basic concepts and application of Theory of Computation.
Apply this basic knowledge of Theory of Computation in the computer field to solve computational problems and in the field of compiler also.
Syllabus: 
Unit NoTopics
Review of Mathematical Background

Sets, Functions, Logical statements, Proofs, Relations, Languages, The Principal of Mathematical induction, the strong principle of Mathematical induction, Recursive definitions, Structural Induction

Regular Languages and Finite Automata

Regular expressions, Regular languages, Memory required to recognize a language, Finite automata, Distinguishable strings, Union, intersection and complement of regular languages.

Nondeterminism and Kleen’s Theorem

Non-deterministic finite automata, Non deterministic finite automata with ^ transitions, Kleen's theorem

Regular and Non Regular Language

Minimization of Finite automata, Non-regular and regular languages, Pumping Lemma, Decision problems and decision algorithms, regular languages in relation to programminglanguages

Context-Free Languages and Push-Down Automata

Context-free languages, Regular Grammars, Derivation tree and ambiguity, An Unambiguous CFG, Simplified and Normal forms, Chomsky normal form

Pushdown Automata and CFL

Push -Down Automata, Definition and examples, Deterministic PDA, Types of acceptances and their equivalence, Equivalence of CFG and PDA, Introduction to parsing, Top-down and bottomup parsing, Non-CFL and CFL, Pumping Lemma for CFL, Intersection and Complement of CFL

Turing Machine

Models of computation, TM definition, Combining TMs, Computing a function with TMs. Variations on Turing Machines, Doubly infinite and more than one Tapes, Non-deterministic and Universal TM

Reference Books: 
Name: 
Introduction to Languages and Theory of Computation
Author: 
By John C. Martin
Name: 
Computation: Finite and Infinite
Author: 
By Marvin L. Minsky
Publication: 
Prentice-Hall, 1967
Name: 
Introduction to formal languages
Author: 
By G. E. Reevsz
Publication: 
Mc-graw hill
Name: 
Formal language theory
Author: 
By M. H. Harrison
Syllabus PDF: 
AttachmentSize
PDF icon 6th Theory of Computation.pdf228.97 KB
branch: 
CBA
BDA
MA
Course: 
2014
2016
Stream: 
B.Tech