Theory of Computation (IT-503)

notes For RGPV Bhopal AICTE Students

Theory of Computation (IT-503) B.Tech RGPV notes AICTE flexible curricula Bachelor of technology

Course Objectives

 Student learns some fundamental concepts in automata theory and designing of Finite Automata, conversion NFA to DFA. Application of Finite Automata in computer science and real world.
 Obtain minimized DFA and Application of regular expression and conversion from RE to Finite Automata and Finite Automata to Regular Expression and Proving language are not regular.
 Designing of CFG’s , Construction of parse trees, finding and removing ambiguity in grammars, simplification of CFG, Conversion of grammar to Chomsky Normal Form ,Greibach normal form.
 Designing problems on Pushdown Automata and conversion of grammar to PDA, PDA to Grammar.
 Designing Turing machines, understanding the working of various types of Turing machines and study P and NP type problem.


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


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.


Course Outcomes

At the completion of the course, students will be able to...
 Convertbetween finite automata, regular grammars, and regular expression representations of regular languages
 Apply the pumping lemma for regular languages to determine if a language is regular
 Convert between grammars and push-down automata for context-free languages
 Determine if a language is regular or context-free
 Demonstrate that a grammar is ambiguous
 Translate a context-free grammar from one form to another
 Produce simple programs for a Turing Machine
 Explain the concept of undecidability
 List examples of undecidable problems


You May Also Like

Contact author here.

Contact Us

Whatsapp :

Click Here

Address :

Indore, Madhya Pradesh