Theory of Computation (IT-5001) - B.E RGPV CBCS & CBGS Scheme Notes -->

## Syllabus

UNIT 1:
Introduction of the theory of computation, Finite state automata – description of finite automata, properties of transition functions, Transition graph, designing finite automata, FSM, DFA, NFA, 2-way finite automata, equivalence of NFA and DFA, Mealy and Moore machines.

UNIT 2:
Regular grammars, regular expressions, regular sets, closure properties of regular grammars, Arden’s theorem, Myhill-Nerode theorem, pumping lemma for regular languages, Application of pumping lemma, applications of finite automata, minimization of FSA.

UNIT 3:
Introduction of Context-Free Grammar - derivation trees, ambiguity, simplification of CFGs, normal forms of CFGs- Chomsky Normal Form and Greibach Normal forms, pumping lemma for CFLs, decision algorithms for CFGs, designing CFGs, Closure properties of CFL’s.

UNIT 4:
Introduction of PDA, formal definition, closure property of PDA, examples of PDA, Deterministic Pushdown Automata, NPDA, conversion PDA to CFG, conversion CFG to PDA.

UNIT 5:
Turing machines - basics and formal definition, language acceptability by TM, examples of TM, variants of TMs – multitape TM, NDTM, Universal Turing Machine, offline TMs, equivalence of single tape and multitape TMs. Recursive and recursively enumerable languages, decidable and undecidable problems – examples, halting problem, reducibility. Introduction of P, NP, NP complete, NP hard problems and Examples of these problems.

## NOTES

• Unit 1
• Unit 2
• Unit 3 (part 1)
• Unit 3 (part 2)
• Unit 4
• Unit 5

## Books Recommended

1. Daniel I.A. Cohen,“Introduction to Computer Theory”,Wiley India.
2. John E. Hopcroft, Jeffrey D.Ullman and Rajeev Motwani, “Introduction to Automata Theory, Languages and Computation”, Pearson Education.
3. K.L.P Mishra & N.Chandrasekaran,“Theory of Computer Science”, PHI Learning.
4. Peter Linz, “Introduction to Automata Theory and Formal Languages”, Narosa Publishing.
5. John C Martin, “Introduction to languages and the theory of computation”, TATA McGraw Hill.

## You May Also Like

#### Services

###### COMPLETELY FREE !!!

Yup, everything is free....

###### NO REGISTRATION REQUIRED

User doesn't have to register for accessing the files, all the files are free & universally accessible without any condition or restriction.

###### RESPONSIVE DESIGN & USER-FRIENDLY

Our webpages are responsive & user-friendly, which means it will automatically adjust according to your device screen size and you will find stuff without ant hustle.

All the files are uploaded on our super-fast servers so that they can be easily downloaded with high speed.

###### NEW PROJECTS

For providing a better experience to our users we are developing our Android application, the application will have a lot of awesome features so stay tuned ;).

###### AWESOME SUPPORT TEAM

Our AI-powered Chatbots are always here to help you so, feel free to ask any question or report if you face any problem. Our team also monitors all chatbots traffic & they will contact you if chatbot fails to help.