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
ContextFree 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:
1. Efim Kinber,
Carl Smith, Theory of Computing: A Gentle introduction,
Prentice- Hall,
2001. ISBN: 0-13-027961-7.
2. John Martin,
Introduction to Languages and the theory of computation, 3rd
Edition, Tata
McGraw Hill, 2003, ISBN:0-07-049939-X
3. 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.
Prerequisite:
Discrete Mathematics, Fundamentals of Computer Programming and Data
structure &
algorithms.
Evaluation and
Grading:
The evaluation and
grading includes the 20% marks for homework assignments and 2 mid
term
exam and 80 % marks
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.
Comments
Post a Comment