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.
The detailed syllabus for Theory of Computation B.Tech (R13) eightsem is as follows
OBJECTIVES: The student should be made to:
- Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine.
- Be aware of Decidability and Un-decidability of various problems.
- Learn types of grammars
UNIT I : FINITE AUTOMATA [9 hours]
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 [9 hours]
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 [9 hours]
Pushdown Automata- Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Equivalence of Pushdown automata and CFL – pumping lemma for CFL – problems based on pumping Lemma.
Download iStudy Android 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.
TOTAL: 45 PERIODS
OUTCOMES: At the end of the course, the student should be able to:
Design Finite State Machine, Pushdown Automata, and Turing Machine.
Explain the Decidability or Undecidability of various problems
TEXT BOOKS:
- Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and Computations”, Second Edition, Pearson Education, 2008. (UNIT 1,2,3).
- John C Martin, “Introduction to Languages and the Theory of Computation”, Tata McGraw Hill Publishing Company, New Delhi, Third Edition, 2007. (UNIT 4,5).
REFERENCES:
- Mishra K L P and Chandrasekaran N, “Theory of Computer Science – Automata, Languages and Computation”, Third Edition, Prentice Hall of India, 2004.
- Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of Computation”, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003.
- Peter Linz, “An Introduction to Formal Language and Automata”, Third Edition, Narosa Publishers, New Delhi, 2002.
- Kamala Krithivasan and Rama. R, “Introduction to Formal Languages, Automata Theory and Computation”, Pearson Education 2009.
For all other B.Tech IT 8th sem syllabus go to Anna University B.Tech Information Technology (IT) 8th Sem Course Structure for (R13) Batch. All details and yearly new syllabus will be updated here time to time.
Do share with friends and in case of questions please feel free drop a comment.