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
225.79 KB
branch:
CBA
BDA
MA
Course:
2018
Stream:
B.Tech