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
1

Review of Mathematical Background

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

2

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.

3

Nondeterminism and Kleen’s Theorem

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

4

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 programming languages

5

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

6

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 bottom-up parsing, Non-CFL and CFL, Pumping Lemma for CFL, Intersection and Complement of CFL

7

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

Text Books: 
Name : 
Introduction to Languages and Theory of Computation
Author: 
By John C. Martin
Edition: 
3rd
Reference Books: 
Name: 
Computation: Finite and Infinite:
Author: 
By Marvin L. Minsky
Publication: 
Prentice-Hall
Edition: 
1967
Name: 
Introduction to formal languages:
Author: 
By G. E. Reevsz
Mc-graw hill.
Syllabus PDF: 
AttachmentSize
PDF icon Theory of Computation.pdf225.79 KB
branch: 
CBA
BDA
MA
Course: 
2018
Stream: 
B.Tech