Skip to content
CampusPrep
IT-503 (A) · Theory of Computation/Official Syllabus

Theory of Computation (IT-503 (A)) - Official Syllabus

1
Unit 1

Introduction of the theory of computation

  • Introduction of the theory of computation
  • Finite state automata – description of finite automata
  • properties of transition functions
  • Transition graph
  • designing finite automata
  • FSM
  • DFA
  • NFA
  • 2-way finite automata
  • equivalence of NFA and DFA
  • Mealy and Moore machines
2
Unit 2

Regular grammars and Expressions

  • Regular grammars
  • regular expressions
  • regular sets
  • closure properties of regular grammars
  • Arden’s theorem
  • Myhill-Nerode theorem
  • pumping lemma for regular languages
  • Application of pumping lemma
  • applications of finite automata
  • minimization of FSA
3
Unit 3

Introduction of Context-Free Grammar

  • Introduction of Context-Free Grammar
  • derivation trees
  • ambiguity
  • simplification of CFGs
  • normal forms of CFGs- Chomsky Normal Form and Greibach Normal forms
  • pumping lemma for CFLs
  • decision algorithms for CFGs
  • designing CFGs
  • Closure properties of CFL’s
4
Unit 4

Introduction of PDA

  • Introduction of PDA
  • formal definition
  • closure property of PDA
  • examples of PDA
  • Deterministic Pushdown Automata
  • NPDA
  • conversion PDA to CFG
  • conversion CFG to PDA
5
Unit 5

Turing machines

  • Turing machines - basics and formal definition
  • language acceptability by TM
  • examples of TM
  • variants of TMs – multitape TM
  • NDTM
  • Universal Turing Machine
  • offline TMs
  • equivalence of single tape and multitape TMs
  • Recursive and recursively enumerable languages
  • decidable and undecidable problems – examples
  • halting problem
  • reducibility
  • Introduction of P
  • NP
  • NP complete
  • NP hard problems and Examples of these problems

Reference Books

  • Introduction to Computer Theory — Daniel I.A. Cohen — Wiley India
  • Introduction to Automata Theory, Languages and Computation — John E Hopcroft, Jeffrey D. Ullman, Rajeev Motwani — Pearson Education
  • Theory of Computer Science — K.L.P Mishra, N.Chandrasekaran — PHI Learning
  • Introduction to Automata Theory and Formal Languages — Peter Linz — Narosa Publishing
  • Introduction to languages and the theory of computation — John C Martin — TATA McGraw Hill
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in