**COURSE OBJECTIVES**

This course will introduce Learners about three foundational areas of computer science namely the basic mathematical models of computation, problems that can be solved by computers and problems that are computationally hard. It also introduces basic computation models, their properties and the necessary mathematical techniques to prove more advanced attributes of these models. The learners will be able to express computer science problems as mathematical statements and formulate proofs.

**COURSE DURATION: 8 Weeks**

COURSE OUTCOMES:

COURSE OUTCOMES:

Upon successful completion of this course, learners will be able to

Interpret the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability

Construct the abstract machines including finite automata, pushdown automata, and Turing machines from their associated languages and grammar

Make use of pumping lemma to show that a language is not regular / not context-free

Construct the grammar for any given finite automata, pushdown automata or Turing machines

Outline the characteristics of P, NP and NP Complete problems

Solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation

**COURSE CONTENTS:**

**AUTOMATA FUNDAMENTALS**

Week 1: Formal Proofs-Finite Automata – deterministic and nondeterministic, regular operations**REGULAR EXPRESSIONS AND LANGUAGES**

Week 2: Regular Expression, Equivalence of DFA, NFA and REs, closure properties

Week 3: Non regular languages and pumping lemma, DFA Minimization,**CONTEXT FREE GRAMMAR AND LANGUAGES**

Week 4: CFGs, Chomsky Normal Form, Non CFLs and pumping lemma for CFLs

Week 5: PDAs, Equivalence of PDA and CFG, Properties of CFLs, DCFLs**PROPERTIES OF CONTEXT FREE LANGUAGES**

Week 6: Turing Machines and its variants- Programming Techniques for TM UNDECIDABILITY

Week 7: Closure properties of decidable languages, Undecidability, Reductions, Post Correspondence Problem

Week 8: Rice's Theorem, introduction to complexity theory, The Class P and NP

**COURSE INSTRUCTORS:**

- Dr.R.Leena Sri
- Dr.M.K.Kavitha Devi
- Dr.K.Sundharakantham