{"id":328,"date":"2016-11-04T07:34:35","date_gmt":"2016-11-04T07:34:35","guid":{"rendered":"http:\/\/www.inspirenignite.com\/anna-university\/?p=328"},"modified":"2019-07-17T07:05:38","modified_gmt":"2019-07-17T07:05:38","slug":"anna-university-b-tech-it-r13-8th-theory-of-computation-detailed-syllabus","status":"publish","type":"post","link":"https:\/\/www.inspirenignite.com\/anna-university\/anna-university-b-tech-it-r13-8th-theory-of-computation-detailed-syllabus\/","title":{"rendered":"Anna University B.Tech IT (R13) 8th Theory of Computation Detailed Syllabus"},"content":{"rendered":"<p>Theory of Computation Syllabus for B.Tech 8th sem is covered here. This gives the details about credits, number of hours and other details along with reference books for the course.<\/p>\n<p>The detailed syllabus for Theory of Computation B.Tech (R13) eightsem is as follows<\/p>\n<p><strong>OBJECTIVES<\/strong>: The student should be made to:<\/p>\n<ul>\n<li>Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine.<\/li>\n<li>Be aware of Decidability and Un-decidability of various problems.<\/li>\n<li>Learn types of grammars<\/li>\n<\/ul>\n<p><strong>UNIT I : FINITE AUTOMATA<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 [9 hours]<br \/>\nIntroduction- Basic Mathematical Notation and techniques- Finite State systems \u2013 Basic Definitions \u2013 Finite Automaton \u2013 DFA &amp; NDFA \u2013 Finite Automaton with \u20ac- moves \u2013 Regular Languages- Regular Expression \u2013 Equivalence of NFA and DFA \u2013 Equivalence of NDFA\u201fs with and without \u20ac-moves \u2013 Equivalence of finite Automaton and regular expressions \u2013Minimization of DFA- &#8211; Pumping Lemma for Regular sets \u2013 Problems based on Pumping Lemma.<\/p>\n<p><strong>UNIT II : \u00a0GRAMMARS<\/strong> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0 [9 hours]<br \/>\nGrammar Introduction\u2013 Types of Grammar &#8211; Context Free Grammars and Languages\u2013 Derivations and Languages \u2013 Ambiguity- Relationship between derivation and derivation trees \u2013 Simplification of CFG \u2013 Elimination of Useless symbols &#8211; Unit productions &#8211; Null productions \u2013 Greiback Normal form \u2013 Chomsky normal form \u2013 Problems related to CNF and GNF<\/p>\n<p><strong>UNIT III : \u00a0PUSHDOWN AUTOMATA \u00a0<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0[9 hours]<br \/>\nPushdown Automata- Definitions \u2013 Moves \u2013 Instantaneous descriptions \u2013 Deterministic pushdown automata \u2013 Equivalence of Pushdown automata and CFL &#8211; pumping lemma for CFL \u2013 problems based on pumping Lemma.<\/p>\n<p style=\"text-align: center\"><strong><a href=\"https:\/\/play.google.com\/store\/apps\/details?id=ini.istudy\" target=\"_blank\" rel=\"noopener\">Download iStudy<\/a> <a href=\"https:\/\/play.google.com\/store\/apps\/details?id=ini.istudy\" target=\"_blank\" rel=\"noopener\">Android<\/a><a href=\"https:\/\/play.google.com\/store\/apps\/details?id=ini.istudy\" target=\"_blank\" rel=\"noopener\"> App for complete Anna University syllabus, results, timetables and all other updates. There are no ads and no pdfs and will make your life way easier.<\/a><\/strong><\/p>\n<p><strong>TOTAL: 45 PERIODS <\/strong><\/p>\n<p><strong>OUTCOMES:<\/strong> At the end of the course, the student should be able to:<\/p>\n<p>Design Finite State Machine, Pushdown Automata, and Turing Machine.<\/p>\n<p>Explain the Decidability or Undecidability of various problems<br \/>\n<strong>TEXT BOOKS<\/strong>:<\/p>\n<ul>\n<li>Hopcroft J.E., Motwani R. and Ullman J.D, \u201cIntroduction to Automata Theory, Languages and Computations\u201d, Second Edition, Pearson Education, 2008. (UNIT 1,2,3).<\/li>\n<li>John C Martin, \u201cIntroduction to Languages and the Theory of Computation\u201d, Tata McGraw Hill Publishing Company, New Delhi, Third Edition, 2007. (UNIT 4,5).<\/li>\n<\/ul>\n<p><strong>REFERENCES:<\/strong><\/p>\n<ul>\n<li>Mishra K L P and Chandrasekaran N, \u201cTheory of Computer Science &#8211; Automata, Languages and Computation\u201d, Third Edition, Prentice Hall of India, 2004.<\/li>\n<li>Harry R Lewis and Christos H Papadimitriou, \u201cElements of the Theory of Computation\u201d, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.<\/li>\n<li>Peter Linz, \u201cAn Introduction to Formal Language and Automata\u201d, Third Edition, Narosa Publishers, New Delhi, 2002.<\/li>\n<li>Kamala Krithivasan and Rama. R, \u201cIntroduction to Formal Languages, Automata Theory and Computation\u201d, Pearson Education 2009.<\/li>\n<\/ul>\n<p>For all other B.Tech IT 8th sem syllabus go to <a href=\"http:\/\/www.inspirenignite.com\/anna-university\/anna-university-b-tech-information-technology-8th-sem-course-structure-for-r13-batch\/\">Anna University B.Tech Information Technology (IT) 8th Sem Course Structure for (R13) Batch.\u00a0<\/a>All details and yearly new syllabus will be updated here time to time.<\/p>\n<p>Do share with friends and in case of questions please feel free drop a comment.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Theory of Computation Syllabus for B.Tech 8th sem is covered here. This gives the details about credits, number of hours and other details along with reference books for the course. [&hellip;]<\/p>\n","protected":false},"author":2259,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-328","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/posts\/328","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/users\/2259"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/comments?post=328"}],"version-history":[{"count":2,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/posts\/328\/revisions"}],"predecessor-version":[{"id":10613,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/posts\/328\/revisions\/10613"}],"wp:attachment":[{"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/media?parent=328"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/categories?post=328"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.inspirenignite.com\/anna-university\/wp-json\/wp\/v2\/tags?post=328"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}