August 06, 2020
Chhattisgarh Swami Vivekanand Technical University, Bhilai
(CSVTU)
(CSVTU)
Branch: Computer Science & Engineering
Semester: V
Subject: Theory of Computation (TOC)
Code: 322554 (22)
UNIT I THE THEORY OF AUTOMATA :
Introduction to automata theory, Examples of automata machine,Finite automata as a language acceptor and translator. Deterministic finite automata. DFA Example, Non deterministic finite automata, NFA Example, finite automata with output (MealyMachine. Moore machine). Finite automata with ? moves, Conversion of NFA to DFAby Arden’s method, Minimizing number of states of a DFA. My hill Nerodetheorem, Properties and limitation of FSM. Two way finite automata. Applicationof finite automata.
UNIT II REGULAREXPRESSIONS :
Regular expression, Properties of Regular Expression. Finite automata and Regular expressions. Regular Expression to DFA conversion &vice versa. Pumping lemma for regular sets. Application of pumping lemma,Regular sets and Regular grammar. Closure properties of regular sets. Decision algorithm for regular sets and regular grammar.
UNIT III GRAMMARS:
Definition and types of grammar. Chomsky hierarchy of grammar. Relation between types of grammars. Role and application areas of grammars. Context free grammar. Left most linear & right most derivation trees. Ambiguity in grammar. Simplification of context free grammar. Chomsky normal from. Greibachnormal form, properties of context free language. Pumping lemma from contextfree language. Decision algorithm for context tree language.
UNIT IV PUSH DOWNAUTOMATA AND TURING MACHINE:
Basic definitions. Deterministic push downautomata and non deterministic push down automata. Acceptance of push downautomata. Push down automata and context free language. Turing machine model.Representation of Turing Machine Construction of Turing Machine for simpleproblem’s. Universal Turing machine and other modifications. Church’sHypothesis. Post correspondence problem. Halting problem of Turing Machine
UNIT V COMPUTABILITY:
Introduction and Basic concepts. Recursive function. Partial recursive function. Partial recursive function. Initial functions, computability, A Turing model for computation. Turing computable functions, Construction of Turing machine for computation. Space and time complexity. Recursive enumerablelanguage and sets.
Text Books :
- Theory of Computer Science (Automata Language & Computation), K.L.P. Mishra and N. Chandrasekran, PHI.
- Introduction to Automata theory. Language and Computation, John E. Hopcropt & Jeffery D. Ullman, Narosa Publishing House.
Reference Books:
- Finite Automata and Formal Languages: A SimpleApproach, A.M. Padma Reddy, Pearson Education, India.
- Theory of Automata and Formal Language, R.B. Patel & P. Nath, Umesh Publication.
- An Introduction and finite automata theory, Adesh K. Pandey, TMH.
- Theory of Computation, AM Natrajan. Tamilarasi, Bilasubramani, New Age International Publishers.
Theory of Computation (TOC) 1st Unit Hand Written Notes Download
Theory of Computation (TOC) 2nd Unit Hand Written Notes Download
Theory of Computation (TOC) 3rd Unit Hand Written Notes Download
Theory of Computation (TOC) 4th Unit Hand Written Notes Download
Theory of Computation (TOC) 5th Unit Hand Written Notes Download
Hand Written Notes of Theory of Computation (TOC)
Theory of Computation (TOC) All Unit Hand Written Notes Download
Theory of Computation (TOC) 1st Unit Hand Written Notes Download
Theory of Computation (TOC) 2nd Unit Hand Written Notes Download
Theory of Computation (TOC) 3rd Unit Hand Written Notes Download
Theory of Computation (TOC) 4th Unit Hand Written Notes Download
Theory of Computation (TOC) 5th Unit Hand Written Notes Download
Previous Year Question Paper of Theory of Computation (TOC)
CSVTU
Theory of Computation (TOC) Previous Year Question paper - 2019
Theory of Computation (TOC) Previous Year Question paper - 2018
Theory of Computation (TOC) Previous Year Question paper - 2017
Theory of Computation (TOC) Previous Year Question paper - 2016
Theory of Computation (TOC) Previous Year Question paper - 2016 Jun
Theory of Computation (TOC) Previous Year Question paper - 2015
Theory of Computation (TOC) Previous Year Question paper - 2015
RGPV
Theory of Computation (TOC) Previous Year Question paper - 2017
Theory of Computation (TOC) Previous Year Question paper - 2016
Theory of Computation (TOC) Previous Year Question paper - 2015
Theory of Computation (TOC) Previous Year Question paper - 2014
Theory of Computation (TOC) Previous Year Question paper - 2013
Theory of Computation (TOC) Previous Year Question paper - 2012
Theory of Computation (TOC) Previous Year Question paper - 2011
Theory of Computation (TOC) Previous Year Question paper - 2011
Theory of Computation (TOC) Previous Year Question paper - 2009
Theory of Computation (TOC) Previous Year Question paper - 2006
Theory of Computation (TOC) Previous Year Question paper - 2005
Theory of Computation (TOC) Previous Year Question paper - 2005
Theory of Computation (TOC) Previous Year Question paper - 2003
Theory of Computation (TOC) Previous Year Question paper - 2003
Theory of Computation (TOC) Previous Year Question paper - 2004
Theory of Computation (TOC) Previous Year Question paper - 2004
Theory of Computation (TOC) Previous Year Question paper - 2002
MCQ of Theory of Computation (TOC)
MCQ of Theory of Computation (TOC) Set 1
MCQ of Theory of Computation (TOC) Set 2
MCQ of Theory of Computation (TOC) Set 3
MCQ of Theory of Computation (TOC) Set 4
MCQ of Theory of Computation (TOC) Set 5
MCQ of Theory of Computation (TOC) Set 6
MCQ of Theory of Computation (TOC) Set 7
MCQ of Theory of Computation (TOC) Set 8
Theory of Computation (TOC) Important / Assignment Question
- Theory of Computation (TOC) Important / Assignment Question All Unit
- Theory of Computation (TOC) Important / Assignment Question Unit 1
- Theory of Computation (TOC) Important / Assignment Question Unit 2
- Theory of Computation (TOC) Important / Assignment Question Unit 3
- Theory of Computation (TOC) Important / Assignment Question Unit 4
- Theory of Computation (TOC) Important / Assignment Question Unit 5
