Theory of Computation

Paper Code: 
MCA 525F
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

 The course will enable the students to

  1. Understand formal mathematical methods used to develop compilers.
  2. Describe finite state automata to create Finite state machines.
  3. Use different types of grammar to solve the problems.
  4. Differentiate between DFA and NDFA using regular languages and regular expressions.
  5. Analyze  various problems of applying normal form techniques, push down automata and Turing Machines
  6. Develop the basic skills necessary to deal with unsolvable problem.

 

Course Learning Outcomes (CLOs):

Learning Outcome (at course level)

Students will be able to:

Learning and teaching strategies

Assessment Strategies

  1. Understand basic concepts and techniques of TOC.
  2. Explain finite state automata,  regular languages and regular expressions
  3. Apply Regular grammar, Context free grammar to solve the problems.
  4. Appraise Turing Machines to test the limits of computation.
  5. Develop skills to measure the complexity and deal with unsolvable problems..

Approach in teaching:

Interactive Lectures,

Modeling, Discussions, implementing enquiry based learning, student centered approach, Through audio-visual aids

 

Learning activities for the students:

Experiential Learning, Presentations, Discussions, Quizzes and Assignments

 

  • Assignments
  • Written test in classroom
  • Classroom Activity
  • Continuous Assessment
    • SemesterEnd Examination

 

12.00
Unit I: 
Review of basic concepts

Graphs, Trees, Strings, Mathematical Induction, finite State Machine - types of languages and Grammars. Overview of Theoretical Computer Science (including computationally intractable problems) - Introduction to System software including various phases / modules in the design of a typical compiler - Chomsky Classification.

 

12.00
Unit II: 
Finite Automata

Introduction to formal proof – Additional forms of proof – Inductive proofs - Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA – Regular Languages- Regular Expression – Equivalence of NFA and DFA - Equivalence of finite Automaton and regular expressions –Minimization of DFA.

12.00
Unit III: 
Grammar

Introduction– Types of Grammar – Context Free Grammars and Languages– Derivations and Languages – Ambiguity- Relationship between derivation and derivation trees – Simplification of CFG – Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL - Pumping Lemma, Parsing ( including LL(1) , SLR and LR(1) Parsing Method).

12.00
Unit IV: 
Turing Machines and Computability Theory

Definition of Turing Machine, Extensions of Turing machines, Non – deterministic Turing machines, Equivalence of various Turing Machine Formalisms, Church – Turing Thesis, Decidability, Halting Problem, Reducibility, Recursion Theorem.

12.00
Unit V: 
Unsolvable Problems and Computable Functions

Unsolvable Problems and Computable Functions – Primitive recursive functions – Recursive and recursively enumerable languages – Universal Turing machine. Measuring and Classifying Complexity: Tractable and Intractable problems- Tractable and possibly intractable problems – P and NP completeness.

ESSENTIAL READINGS: 
  1. John C. Martin, “Introduction to Languages and the Theory of Computation”,Fourth Edition, McGraw-Hill, 2010
  2. Michael Sipser, “Introduction to the Theory of Computation”, Third Edition, Cengage Publication, 2012
REFERENCES: 
  1. Wayne Goddard, “Introducing the Theory of Computation”, Jones & Bartlett India Pvt.Ltd, 2009.
Academic Year: 
2019-20
  • Printer-friendly version