{"id":1187,"date":"2022-01-28T20:51:10","date_gmt":"2022-01-28T20:51:10","guid":{"rendered":"https:\/\/itgeeks.in\/home\/?p=1187"},"modified":"2022-01-28T20:51:11","modified_gmt":"2022-01-28T20:51:11","slug":"2k6cs-503-theoretical-foundation-of-computation-it-503-theory-of-automata-formal-languages%ef%bf%bc","status":"publish","type":"post","link":"https:\/\/itgeeks.in\/home\/?p=1187","title":{"rendered":"2K6CS 503: THEORETICAL FOUNDATION OF COMPUTATION \/ IT 503 THEORY OF AUTOMATA & FORMAL LANGUAGES\ufffc"},"content":{"rendered":"\n

Module I (14 hours)<\/strong>
Introduction; alphabets, Strings and Languages; Automata and Grammars -Finite automata (FA) -DFA-NFA \u2013 Finite Automata with epsilon-transitions-Equivalence of DFAs and NFAs -Regular expressions (RE) -Definition, RE to FA, FA to RE, algebraic laws for RE, applications of REs. -Regular grammars and FA -Proving languages to be non-regular -Pumping Lenma \u2013 Applications. Closure properties of Regular languages -Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. \u2013Myhill-Nerode theorem-DFA Minimization – Decision properties of Regular languages – Two-way finite automata, Finite automata with output.
Module II (13 hours)<\/strong>
Context-free Grammars (CFG) -Parse tree – Ambiguity in grammars and Languages-Applications of CFGPushdown Automata (PDA) -Equivalence of PDAs and CFGs -DPDAs -Definition, DPDAs and Regular Languages,-DPDA and Ambiguous grammars–CYK algorithm -Simplification of CFGs -Normal forms -CNF and GNF –Pumping lemma for CFLs,Closure properties of CFLs – Decision properties of CFL.
Module III (13 hours)<\/strong>
Turing Machines -Formal definition and behavior – TM as a computer of integer functions -Programming techniques for TMs -Storage in state, multiple tracks, subroutines, etc.-Computing a partial function with Turing machineVariants of TMs \u2013Multitape TMs, Nondeterministic TMs. -TMs with semi-infinite tapes, multistack machines.- universal Turing Machines-Equivalence of the various variants with the basic model- Models of computation and Church-Turing Thesis.
Module IV (13 hours)<\/strong>
Computability \u2013 Closure properties of recursive and recursively enumerable language. Undecidability- A language that is not RE \u2013 An undecidable problem that is RE \u2013 Undecidable problems about TM-Halting problem \u2013 Post Correspondence Problem \u2013 The Chomsky hierarchy \u2013 Context sensitive language and LBA \u2013Equivalence of LBA and CSG.<\/p>\n\n\n\n

Text books<\/strong>
1.\u00a0J E Hopcroft And J D Ullman : Introduction to Automata Theory and Computation, Addison Wesley<\/a>
2.\u00a0John C Martin : Introduction to Languages and the Theory of Computation(3 rd Edition) , TMH<\/a><\/p>\n\n\n\n

Reference books<\/strong>
1.\u00a0H R Lewis and C H Papadimitriou : Elemnts of Theory of Computation<\/a>
2.\u00a0Sipser : Introduction to theory of Computation, CENAGE LEARNING Indian Edition<\/a>
3.\u00a0Linz P : An Introduction to Formal Languages and Automata, Narosa<\/a>\u00a0\u00a0<\/p>\n\n\n\n

\n
S5 Question Papers<\/a><\/div>\n\n\n\n
Notes<\/a><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Module I (14 hours)Introduction; alphabets, Strings and Languages; Automata and Grammars -Finite automata (FA) -DFA-NFA \u2013 Finite Automata with epsilon-transitions-Equivalence<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,49,20,9,8],"tags":[7],"class_list":["post-1187","post","type-post","status-publish","format-standard","hentry","category-ku-s5-cse","category-ku-s5-it","category-ku-syb-s5","category-ku-syllabus","category-syllabus","tag-kannur-university"],"_links":{"self":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/1187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1187"}],"version-history":[{"count":1,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/1187\/revisions"}],"predecessor-version":[{"id":1200,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=\/wp\/v2\/posts\/1187\/revisions\/1200"}],"wp:attachment":[{"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itgeeks.in\/home\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}