Complete Lecture notes on Theory Of Computation

Complete lecture notes of theory of computation based on the syllabus of Tribhuwan University (IOE) Introduction:  It includes...

Complete lecture notes of theory of computation based on the syllabus of Tribhuwan University (IOE)

Introduction: 

It includes introduction to set, relation, function, Proof techniques and alphabets, language, regular expression. Read: PDF note of Chapter 1 – Introduction to Theory of Computation.

Finite Automata:

 The second chapter aims to provide general information on Finite Automata (Deterministic and Non‐Deterministic), equivalence of regular language and finite automata, regular language and its properties, Pumping lemma for regular language & decision algorithms for regular languages. Download: PDF note of 

Chapter 2 – Finite Automata.

Context free language: 

The third chaper mainly concerns with context free language & grammar and their simplification, derivative trees, Chomsky normal form (CNF), Push Down Automata (PDA) and its equivalence with context free language (CFL). Apart from these, it includes Pumping lemma for context free language and Decision algorithms for context free language. Download: Note of Chapter 3 – Context Free Language.

Turing machine:

 Fourth Chapter deals with turing machine ( its definition, notation & Computation), Extensions of Turing machine and Unrestricted grammar including Recursive function theory. Read: Chapter 4 Note – Turing Machine.

Undecidability:

 Chapter 5 includes the micro syllabus of computational complexity, Class P & NP complete problems. 

Chapter6
Computational Complexity.

Chapter6