Theory of Computation(CMA705)

Course Name: 

Theory of Computation

Programme: 

M.Tech (CMA)

Semester: 

Second

Category: 

Programme Core (PC)

Credits (L-T-P): 

(3-0-0)3

Content: 

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.

References: 

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.

Department: 

Mathematical and Computational Sciences
 

Contact us

Dr. P. Sam Johnson, 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.