Copyright 2017 - CSIM - Asian Institute of Technology

Theory of Computing

Course code: AT70.03
Credits: 3(3–0)
This course is required

Course objectives

To provide an exposure to the theory of formal languages, automata and complexity theory.

Learning outcome

Finite Automata and Regular Expressions. Properties of Regular Sets. Context-Free Grammars. Pushdown Automata. Properties of Context-Free Languages. Turing Machines. Undecidability. Computational Complexity Theory. Intractable Problems.

Course outline

I.        Finite Automata and Regular Expressions
1.     Finite State Systems
2.     Non-deterministic Finite Automata
3.     Regular Expressions
 
II.      Properties of Regular Sets
1.     The Pumping Lemma for Regular Sets
2.     Closure Properties of Regular Sets
3.     Decision Algorithms for Regular Sets
 
III.     Context-Free Grammars, Pushdown Automata
1.     Derivation Trees
2.     Simplication of Context-Free Grammars
3.     Normal Forms
4.     Pushdown Automata
5.     Properties of Context-Free Languages: The Pumping Lemma for CFL's, Closure Properties of CFL's, Decision Algorithms for CFL's
 
IV.     Turing Machines
1.     Computable Languages and Functions
2.     Church's Hypothesis
 
V.      Undecidability
1.     Properties of Recursive and Recursively Enumerable Languages
2.     Universal Turing Machines and Undecidable Problem
3.     Recursive Function Theory
 
VI.     The Chonsky Hierarchy
 
VII.   Computational Complexity Theory: Tractability and Intractability
1.     Deterministic Turing Machines and the Class P
2.     Nondeterministic Turing Machines and the Class NP
3.     Relationship between P and NP
4.     Polynomial Transformation and NP-Completeness
5.     Cook’s Theorem
6.     NP-Complete Problems
7.     NP-Hardness

Learning resources

Textbook

H.R. Lewis, C.H. Papadimitriou:
        Element of the Theory of Computation, Prentice Hall, 2nd Edition, 1998.

Reference books

C. Calude:
        Theories of Computational Complexity, North Holland, 1988.
 
M. Chandrasekaran, and K.L.P. Mishra:
        Theory of Computer Science: Automata, Language and Computation, Prentice Hall, 1995.
 
J.E. Hopcroft, J.D. Ullman:
        Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Massachusetts, 1979.
 
M. Sipser:
        Introduction to the Theory of Computation, Pws Pub Co, USA, 1996.
 
C.H. Smith:
        A Recursive Introduction to the Theory of Computation, Springer Verlag, 1994.
 
R.G. Taylor:
        Model of Computation and Formal Languages, Oxford University Press, 1997.
 
M.R. Garey and D. S. Johnson:
        Computer and Intractability, W.H. Freeman and Company, New York, 1979.

Grading

The final grade will be computed from the following constituent parts:
 
Mid-semester exam       - (30%)
Final exam                    - (70%)
 
Open-book examination is used for both mid-semesterand final exam.

Back to the list

 

Login Form

Search

School of Engineering and technologies     Asian Institute of Technology