Skip to content
CampusPrep
CS-501 · Theory of Computation/Official Syllabus

Theory of Computation (CS-501) - Official Syllabus

1
Unit 1

Introduction of Automata Theory

  • Examples of automata machines
  • Finite Automata as a language acceptor and translator
  • Moore machines
  • mealy machines
  • composite machine
  • Conversion from Mealy to Moore and vice versa
2
Unit 2

Types of Finite Automata

  • Non Deterministic Finite Automata (NDFA)
  • Deterministic finite automata machines
  • conversion of NDFA to DFA
  • minimization of automata machines
  • regular expression
  • Arden's theorem
  • Meaning of union
  • intersection
  • concatenation
  • closure
  • 2 way DFA
3
Unit 3

Grammars

  • Types of grammar
  • context sensitive grammar
  • context free grammar
  • regular grammar
  • Derivation trees
  • ambiguity in grammar
  • simplification of context free grammar
  • conversion of grammar to automata machine and vice versa
  • Chomsky hierarchy of grammar
  • killing null and unit productions
  • Chomsky normal form
  • Greibach normal form
4
Unit 4

Push down Automata

  • example of PDA
  • deterministic and non-deterministic PDA
  • conversion of PDA into context free grammar and vice versa
  • CFG equivalent to PDA
  • Petrinet model
5
Unit 5

Turing Machine

  • Techniques for construction
  • Universal Turing machine
  • Multitape
  • multihead
  • multidimensional Turing machine
  • N-P complete problems
  • Decidability and Recursively Enumerable Languages
  • decidability
  • decidable languages
  • undecidable languages
  • Halting problem of Turing machine
  • the post correspondence problem

Laboratory Experiments

  • Design a Program for creating machine that accepts three consecutive one.
  • Design a Program for creating machine that accepts the string always ending with 101.
  • Design a Program for Mode 3 Machine
  • Design a program for accepting decimal number divisible by 2.
  • Design a program for creating a machine which accepts string having equal no. of 1's and 0's.
  • Design a program for creating a machine which count number of 1's and 0's in a given string.
  • Design a Program to find 2's complement of a given binary number.
  • Design a Program which will increment the given binary number by 1.
  • Design a Program to convert NDFA to DFA.
  • Design a Program to create PDA machine that accept the well-formed parenthesis.
  • Design a PDA to accept WCWR where w is any string and WR is reverse of that string and C is a Special symbol.
  • Design a Turing machine that's accepts the following language an b n c n where n>0.

Reference Books

  • Introduction to Automata Theory Language & Computation — Hopcroft, Ullman — Narosa Publication
  • Element of the Theory Computation — Lewis, Christors — Pearson
  • Theory of Computation — Chandrasekhar, Mishra — PHI
  • Theory of Computation — Wood — Harper & Row
  • Introduction to Computing Theory — Daniel I-A Cohen — Wiley
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