Theory of Computation(CMA705)

Course Name: 

Theory of Computation


M.Tech (CMA)




Programme Core (PC)

Credits (L-T-P): 



Introduction, Abstract Models for Computation and their relationship with formal languages and Theory of Recursive Functions; Computational and Representational System Models: Finite Automata; Push-down Automata; Linear Bounded Automata; Turing Machines; Formal Language Models; Regular Expressions, Context free Languages, Context Sensitive Languages, Recursively, Enumerable Languages, Generative Grammars, Recognition Procedures; Finite Representation for formal languages, Chomsky Hierarchy; Normal Forms; Derivation Graphs; Pumping Lemma; Undecidability; Recursive Functions and Computability; Computational Effectiveness, Complexity Measures, Reducibility; Complexity Classes.


Hopcroft and Ullman, Introduction to Automata Theory; Languages and Computation, Narosa.
Gyorgy E. Revesz, Introdution to Formal Languages, Dover.
Aho, Hopcraft & Ullman, Automata, Languages and Computation, Narosa, 1986
Mishra and Chandrashekar, Theory of Computer Science, Prentice Hall of India, 1999.


Mathematical and Computational Sciences

Contact us

Shyam S Kamath, Professor and Head
Department of MACS, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.

  • Hot line: +91-0824-2474048

Connect with us

We're on Social Networks. Follow us & get in touch.