Theory of Computation(CMA705)
Course Name:
Theory of Computation
Programme:
Semester:
Category:
Credits (L-T-P):
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.