CS6503 THEORY OF COMPUTATION SYLLABUS

UNIT I-FINITE AUTOMATA

Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & 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

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

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

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

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.

theory of computation syllabus

PREFERRED SEARCHES :

We didn’t restrict ourselves with book knowledge.Providing support in hardware and software sides.We experiment some best ideas and provided to you.It’s our first blog created to help user’s.Theory of Computation Syllabus.To gain some knowledge about hard ware/software click here.

We are also preferring you some official sites.To learn something other than studies mail us.Join us in social medias.Facebook,Google+,etc.We will help you regarding project works also.Feel free to contact us.Ready to help you.Response for your mail will be done as quick as possible.Within short span of 24 hours.Also providing contents for other subjects.Contents will be easy to read.Help you to gain more marks.Share our site with your friends.Help them to gain more knowledge and also marks in academics.Theory of Computation Syllabus.Theory of Computation Syllabus.

Feel comfortable with our contents.For more contents you can mail us.Mail your needs we will provide if possible.Theory of Computation Syllabus.

For further subjects syllabus, notes, video materials and question papers visit kprblog.in.

To share your thoughts mail us.For further queries or suggestions.Mail us to kprblog.in@gmail.com.

Like our blog page in facebook.@ Tips and tricks.

Latest posts by admin (see all)

More in sem5
OOAD SYLLABUS

OOAD SYLLABUS CS6502 [OBJECT ORIENTED ANALYSIS AND DESIGN]   UNIT I-UML DIAGRAMS Introduction to OOAD – Unified Process - UML diagrams...

Close