Course Title: Theory of Computation
Course no: CSC-251 Full Marks: 80+20
Credit hours: 3 Pass Marks: 32+8
Nature of course: Theory (3 Hrs.)
Course Synopsis: Deterministic and non-deterministic finite state machines, regular expressions, languages and their properties. Context free grammars, push down automata, Turing machines and computability, undecidable and intractable problems, and Computational complexity.
Goal: To gain understanding of the abstract models of computation and formal language approach to computation.
Course contents:
Unit 1: 14 Hrs.
1.1 Review of Mathematical Preliminaries: Sets, Logic, Functions, Relations, Languages, Proofs.
1.2 Finite Automata: Deterministic and Non-deterministic Finite Automata, Equivalence of Deterministic and Non-deterministic Finite Automata, Finite Automata with Epsilon-Transition.
1.3 Regular Expressions and Languages, Equivalence of Regular Expressions and Finite Automata, Algebraic Laws for Regular Expressions, Properties of Regular Ranguages, Pumping Lemma for Regular Languages, Minimization of Finite State Machine.
Unit 2: 11 Hrs.
2.1 Context-Free Grammar, Parse Trees, Derivation and Ambiguity, Normal Forms(CNF and GNF) of Context-Free Grammar, Regular Grammars, Closure Properties of Context-Free Languages, Proving a Language to be Non-Context-Free.
2.2 Push Down Automata (PDA), Language of PDA, Deterministic and Non-deterministic PDA, Equivalence of PDA's and CFG,s.
Unit 3: 10 Hrs.
3.1 Introduction to Turing Machines, Computation by Turing Machines, Variants of Turing Machines, Non-deterministic Turing Machines, Turing Enumerable Languages.
3.2 Church's Thesis and Algorithm, Universal Turing Machines, Halting Problems, Turing Machines and Computers.
Unit 4: 10 Hrs.
4.1 Undecidability: Recursive and Recursively Enumerable Languages, Encoding of Turing Machine, Universal Language, Unrestricted Grammars and Chomsky Hierarchy, Unsolvable Problems by Turing Machines, Undecidable Problems, Post's Correspondence Problem.
4.2 Computational Complexity and Intractable Problems, Measuring Complexity, Class P, Class NP, NP-Completeness and Problem Reduction , NP-Complete Problems.
Text Book:
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001. ISBN: 81-7808-347-7
References:
Efim Kinber, Carl Smith, Theory of Computing: A Gentle introduction, Prentice- Hall, 2001. ISBN: 0-13-027961-7.
John Martin, Introduction to Languages and the theory of computation, 3rd Edition, Tata McGraw Hill, 2003, ISBN:0-07-049939-X
Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd Edition, Prentice Hall, 1998.
Homework Assignments:
Homework assignments will be given through out the semester covering the lecture materials in each unit. The homework assignment will cover the 30% of the internal evaluation.
Pre-requisite: Discrete Mathematics, Fundamentals of Computer Programming and Data structure & algorithms.
Evaluation and Grading:
The evaluation and grading includes the 20% weitage for homework assignments and 2 mid term exam and 80 % weitage for final semester exam. The grading of the 20% internal evaluation will be as:
Homework assignment: 30% (6 marks)
First Mid-term exam: 30% (6 marks)
Second Mid-term exam: 40% (8 marks)
Homework assignment will be given in each weekend.
First Mid-Term: After completion of Unit 1.
Second Mid-Term: After Completion of Unit 3.
0 comments:
Post a Comment