Back close
Admissions

Course Detail

Course Name Theory of Computation
Course Code 25CSA332
Program B. Sc. in Physics, Mathematics & Computer Science (with Minor in Artificial Intelligence and Data Science)
Semester Electives: Computer Science
Campus Mysuru

Syllabus

Unit I

Introduction to Theory of Computation, Languages and Strings, Computation, Finite StateMachines (FSM): Formal Definition of a DFA, Deterministic Finite Automata, Regularlanguages, Designing DFA, Formal Definition of an NDFA, Nondeterministic NDFAs,Minimizing States, NDFA to DFA Conversion

Unit II

Regular Expressions (RE) introduction to RE, Some RE Examples, Applications of REs,
Manipulating and Simplifying REs. Regular Grammars: Definition- Regular Grammars andRegular languages. Regular Languages (RL) and Non regular Languages. Properties of RLs,Canonical form of Regular languages. Pumping Lemma for Regular Grammars.

Unit III

Context-Free Grammars (CFG): CFGs and languages, designing CFGs, simplifying CFGs,Derivation and Parse trees, Ambiguity, Normal Forms. Chomsky Normal Form (CNF), GreibachNormal Form, Pumping Lemma for CFG.

Unit IV

Pushdown Automata (PDA): Definition of non-deterministic PDA, Deterministic and Nondeterministic PDAs, Non-determinism and Halting. PDA & Context-Free Grammar.

Unit V

Introduction to Turing machines-Variants of Turing Machines (TM), the model of LinearBounded automata: Decidability: Definition of an algorithm, decidability, decidable languages,undecidable languages, halting problem of TM, -Complexity: Growth rate of functions, theclasses of P and NP.

Objectives and Outcomes

OBJECTIVE: The course introduces various computation models like Finite State Automata,Push down Automata and Turing machine and also to be aware of decidability and undesirabilityof various problems.

CO1 To understand the theory and practice of theory of computation, languages
CO2 To learn finite state machines used in computers
CO3 To learn context free grammars, parsing techniques.
CO4 To understand thePushdown Automata
CO5 To learn about Turing Machines (TM) used in decidability and NP Problems

 

CO-PO Affinity Map
PO/CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PSO1 PSO2 PSO3 PSO4
CO1 1 0 3 2 1 0 1 0 0 0 2
CO2 1 0 2 1 1 0 1 0 1 1 2
CO3 0 0 1 1 1 0 1 0 1 0 2
CO4 0 0 1 1 1 0 1 0 1 1 2
CO5 1 0 1 1 1 0 1 0 1 1 2

Text Books / References

TEXT BOOKS:

  • Elaine Rich, Automata, Computability and Complexity, 1st Edition, Pearson

Education,2012/2013

  • K L P Mishra, N Chandrasekaran , 3rd Edition, Theory of Computer Science, PhI, 2012.

REFERENCES:

  • John E Hopcroft, Rajeev Motwani, Jeffery D Ullman, Introduction to Automata Theory,Languages, and Computation, 3rd Edition, Pearson Education, 2013
  • Michael Sipser : Introduction to the Theory of Computation, 3rd edition, Cengage learning,2013
  • John C Martin, Introduction to Languages and The Theory of Computation, 3rd Edition, Tata
  • McGraw –Hill Publishing Company Limited, 2013
  • Peter Linz, “An Introduction to Formal Languages and Automata”, 3rd Edition, NarosaPublishers, 1998
  • Basavaraj S. Anami, Karibasappa K G, Formal Languages and Automata theory, Wiley India,2012

 

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now