Theory of Computation(314442)

THEORY OF COMPUTATION 314442

Unit I: Basic Concept.

Symbol/alphabets, string/word, language, formal language, natural and formal language Basic Machine, Finite State machine: state tables, transition graph, acceptance and regection Regular Expressions : Formal definition, Recursive definition of regular expression, regular set, identities of regular expressions. Languages associated with regular expression. Kleene closure.

Unit II: Finite automata(FA)

Definition of FA, representation (tabular form of state transition function and machine transition function, transition graphs, and adjancy matrix),finite control of FA over string, language acceptance by FA., deterministic finite automaton(DFA) and non-deterministic finite automaton(NFA),concept of moves, NFA with e moves, NFA without e moves, removal of e moves, conversion of NFA without e moves to DFA, conversion of NFA with e moves to DFA, FA with output: Moore and mealey machines-definition, models, inter conversion

Unit III: Contexts Free Grammars and languages

Phrase structure grammar, context free grammar, context free languages(CFL), Production rules, formalization, derivation and derivation trees, ambiguous grammar, removal of ambiguity and inherent ambiguity, simplification of grammar-removal of unit production, useless production, useless symbol, and production; normal forms(ch0masky normal form and greibach normal form), Chomsky hierarchy.

Unit IV: Regular Grammar and CFL

Regular Grammar: Definition, left linear and right linear regular grammer, regular grammer and finite automata,FA to RG and RG to FA, inter conversion between left linear and right linear regular grammar.CFL: Properties,normal forms,etc.Pumping lemma of CFL, definition of/for CFl and application automata theory

Unit V: Push down automata(PDA)

Definition, deterministic, pushes down automata(DPDA), non-deterministic push down automata(NPDA), the language of PDA. Equivalance of PDA’s and CFG’s ,clousure properties of CFL’s. Concept of post machines.

Unit VI: Turning Machine

Definition and example of TM, recursive sets, partial recursive function, recursively enumerable sets, computing a partial function with TM, combining TM’s variations of TM: Multi-tape TM’s, universal TM, model of computation and church’s turing hypothesis, unsolvable problem,TM’s halting problem

Reference:Syllabus copy - T E I.T.2008 pattern ( unipune.ac.in )

Text Books:

1. Daniel I.A.Cohen,"Introduction to automata theory languages and computations”, Pearson education asia,second edition

2. John C. martin,” Introduction to language and theory of computation”, TMH, 3rd edition.

Reference Books:

1. Hopcroft Ulman, “Introduction to automata theory, languages and computations”, Pearson education Asia, 2nd edition

2. E V Krishnamurthy,”Introduction to Theory of Computer Science”, EWP Second 2nd edition.

3. K.L.P Mishra,N.Chandrasekaran,” Theory of computer science(automata, languages and computation)”, Prentice hall india, 2nd edition