Theory of ComputationUploaded by: MYcsvtu Notes
Shared by: Mukul Joshi
2. Unit-2
3. Unit-3
4. Unit-4
5. Unit-5
Theory of Computation Books__________________________________
Shared by: Priya Jain
|
Theory of Computation SyllabusUNIT-1. THE THEORY OF AUTOMATA : Introduction to automata theory, Examples of automata machine, Finite automata as a language acceptor and translator. Deterministic finite automata. Non deterministic finite automata, finite automata with output (Mealy Machine. Moore machine). Finite automata with ? moves, Conversion of NFA to DFA by Arden’s method, Minimizing number of states of a DFA. My hill Nerode theorem, Properties and limitation of FSM. Two way finite automata. Application of finite automata. UNIT-2. REGULAR EXPRESSIONS : Regular expression, Properties of Regular Expression. Finite automata and Regular expressions. Regular Expression to DFA conversion & vice versa. Pumping lemma for regular sets. Application of pumping lemma, Regular sets and Regular grammar. Closure properties of regular sets. Decision algorithm for regular sets and regular grammar. UNIT-3. GRAMMARS. Definition and types of grammar. Chomsky hierarchy of grammar. Relation between types of grammars. Role and application areas of grammars. Context free grammar. Left most linear & right most derivation trees. Ambiguity in grammar. Simplification of context free grammar. Chomsky normal from. Greibach normal form, properties of context free language. Pumping lemma from context free language. Decision algorithm for context tree language. UNIT-4. PUSH DOWN AUTOMATA AND TURING MACHINE. Basic definitions. Deterministic push down automata and non deterministic push down automata. Acceptance of push down automata. Push down automata and context free language. Turing machine model. Representation of Turing Machine Construction of Turing Machine for simple problem’s. Universal Turing machine and other modifications. Church’s Hypothesis. Post correspondence problem. Halting problem of Turing Machine UNIT-5 COMPUTABILITY Introduction and Basic concepts. Recursive function. Partial recursive function. Partial recursive function. Initial functions, computability, A Turing model for computation. Turing computable functions, Construction of Turing machine for computation. Space and time complexity. Recursive enumerable language and sets. |