Theory of Computation [V Semester CSE]

Author: A.A. Puntembekar " V Semester CSE"

No Customer Reviews

Add to Wishlist

Bulk Orders

Rs. 299.25 + Shipping Charges

Price: Rs. 315.00 5% Offer

In stock.

Sold by : Sri Markandeya Book Depot

Quantity

Check delivery option

Availability

Publisher	Technical Publications
Product Format	Paper Back
Language Published	English
Volume Number	--
Number of Pages	--
Product ID	9789333202077

Theory of Computation :

UNIT I Finite Automata (Chapters - 1, 2)

Introduction - Basic mathematical notation and techniques - Finite state systems - Basic definitions - Finite automaton - DFA and NDFA - Finite automaton with - moves - Regular languages - Regular expression - Equivalence of NFA and DFA - Equivalence of NDFA’s with and without -moves - Equivalence of finite automaton and regular expressions - Minimization of DFA - Pumping lemma for regular sets - Problems based on pumping lemma.

UNIT II Grammars (Chapter - 3)

Grammar introduction - Types of grammar - Context free grammars and languages - Derivations and languages - Ambiguity - Relationship between derivation and derivation trees - Simplification of CFG - Elimination of useless symbols - Unit productions - Null productions - Greiback normal form - Chomsky normal form - Problems related to CNF and GNF.

UNIT III Pushdown Automata (Chapter - 4)

Pushdown automata - Definitions - Moves - Instantaneous descriptions - Deterministic pushdown automata - Equivalence of pushdown automata and CFL - Pumping lemma for CFL - Problems based on pumping lemma.

UNIT IV Turing Machines (Chapter - 5)

Definitions of Turing machines - Models - Computable languages and functions -Techniques for Turing machine construction - Multi head and multi tape Turing machines - The halting problem - Partial solvability - Problems about Turing machine - Chomskian hierarchy of languages.

UNIT V Unsolvable Problems and Computable Functions (Chapter - 6)

Unsolvable problems and computable functions - Primitive recursive functions - Recursive and recursively enumerable languages - Universal Turing machine. Measuring and classifying complexity : Tractable and intractable problems - Tractable and possibly intractable problems - P and NP completeness - Polynomial time reductions.