Preamble

This course aims to answer perhaps the most important question in computer science - What are the capabilities and limitations of modern computers? Here we study computability - what can be computed, complexity theory - how simple or difficult is the problem to be solved, and models of computation - Finite Automata, PDA, and Turing machines along with their variants in the context of formal languages, their generators, and their recognizers.
   

---

Course Contents

In this course, we cover [RGPV Syllabus ]

Topics	Lecture Slides	Recommended Readings
	Lecture Slides #0
Finite Automata, Strings and Languages, Deterministic and non-deterministic FSMs, Equivalence of DFA and NDFA, Closure properties of Regular Languages. Mealy & Moore machines, Minimization of finite automata, Myhill- Nerode theorem, Two-way finite automata. Regular Operations, Regular sets, Regular expressions and Regular Languages Pumping lemma, Application of pumping lemma,	Lecture Slides #1 Lecture Slides #2 Lecture Slides #6 Lecture Slides #5 Lecture Slides #3 Lecture Slides #4 Lecture Slides #9
CFG and Push Down Automata (PDA) Definition, Formal Grammar Regular and Context –Free Grammars, Derivation trees and Ambiguity, Normal Forms (Chomsky Normal Form and Greibach Normal forms). Deterministic PDA, Equivalence of PDA and CFG. The pumping lemma for CFL’s, Closure properties of CFL’s, Decision problems involving CFL’s.	Lecture Slides #10 Lecture Slides #11 Lecture Slides #16 Lecture Slides #17 Lecture Slides #18
Turing Machines (TM) Introduction, TM model, representation and languages acceptability of TM, Design of TM, Universal TM & Other modification,	Lecture Slides #19,20 Lecture Slides #21 Lecture Slides #22
Computability Church’s hypothesis, composite & iterated TM. Turing machine as enumerators. Properties of recursive & recursively enumerable languages,	Lecture Slides #23,24 Lecture Slides #25
Complexity Theory Tractable and Un-tractable Problems: P, NP, NP complete and NP hard problems, examples of these problems like satisfiability, problems, vertex cover problem, Hamiltonian path problem, traveling sales man problem, Partition problem etc.	Lecture Slides #26 Lecture Slides #27,28, 29, 30
Other Lectures and Tutorials	Mid-Semester-Test-1 Assignment #1

---

References

    1. Michael Sipser. Introduction to the Theory of Computation, Second Edition, Cenage Learning, India
    2. Hopcroft, Ullman, Motwani. Introduction to Automata Theory, Languages, and Computation, 3/E, Pearson Education.

---

Meeting Time
    Monday and Tuesday: 3.10 - 4.00 pm
    Thursday and Friday: 12.10 - 1.00 pm
    Wednesday: 3.10 - 4.00 pm (Tutorial)

---

 

---

Assignments
    Assignment #1: Due date October 05, 2009 [Helpful in preparing for MST-1]
  

---

Mid-Semester Exam

---

Overall Internal Evaluation

        20% Assignments
        80% Mid-Semester Exams

There will be bonus marks (max 10%) for undertaking additional work on course objectives.
All the submissions must be mailed to the submission portal at uit.submission@gmail.com

---

Announcements

    1. [18.09.2009] Assignment is uploaded, Submit it on or before October 5, 2009 at 12 pm (midnight). Submission portal uit.submission@gmail.com
    2. [24.09.2009] The syllabus for the 1st mid semester test [MST] includes UNIT-1 except Pumping Lemma and its applications.