Copyright 2018 - 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.     Co

Learning resources

Textbook

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

Journals

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.
 

Login Form

Search

School of Engineering and technologies     Asian Institute of Technology