# Theory of Computation (IT-503)

## 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.

• Unit 1
• Unit 2
• Unit 3
• 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.

## 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.