'Theory of Computation' is a course offered in the fifth semester of B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.
Unit 1
Automata and Languages: Chomsky hierarchy of languages, Introduction Finite Automata - Regular Expressions - Nondeterministic Finite Automata - equivalence of NFAs and DFAs – Minimization of DFA.
Unit 2
Regular Expressions - Non-Regular Languages - Pumping Lemma for regular languages.
Unit 3
Parse tree derivations (top-down and bottom-up) Context free languages – Chomsky normal form, GNF - Push Down Automata - Pumping lemma for context free language. CYK Algorithm, Deterministic CFLs. Ambiguous grammar, removing ambiguity, Computability Theory: Turing Machines - Non-deterministic Turing Machines – CSG, Undecidability - PCP Computation histories – Reducibility.