Theory of Computation

Introduction to Set theory: Definition of sets and Subsets, Properties and operations, Type of Sets: Countability – Unaccountability sets, Relations and Functions, closure of relations, Type of functions: Primitive recursive and partial recursive functions, Computable and non computable functions. Fundamentals Formal representation of languages: Strings, Alphabet, grammar, Language, Operations, Chomsky Classification, languages and their relationships, Recursively enumerable set.

Introduction to Automata theory: Definition of Automation ,Finite Automata, Formal definition, Language acceptability by Finite Automata, Transition Diagrams and Transition systems, Deterministic and Nondeterministic finite automation, Finite Automation with- Transitions, Mealy and Moore Models, Conversion of NFA to DFA –-Transitions, Eliminating  Regular operations, Regular sets and Regular Expressions, Pumping lemma for regular languages, Applications of finite state automata :Lexical analyzers and Text search.

Context free language: Derivation tree, Ambiguity in Context free grammar, Simplification of CFG, Normal Forms, Pumping lemma for Context free languages.
Pushdown Automata: Formal definition, Language acceptability by PDA, Deterministic and nondeterministic PDA, Context free grammar, Applications of PDA – Parsing.

Turing Machines: Formal definition, Language acceptability, Universal Turing Machines – Halting Problem of Turing Machines, Linear bounded automaton.

Algorithm: definition of algorithm and decidability, Algorithmic complexity, Tractable and intractable problems, Church’s Thesis. , Complexity classes, Class P, Class NP, NP Complete and NP Hard problems.