Skip to content
CampusPrep
AL-601 · Theory of Computation/Official Syllabus

Theory of Computation (AL-601) - Official Syllabus

1
Unit 1

Introduction of Automata Theory

  • Examples of automata machines
  • Finite Automata as a language acceptor
  • Finite Automata as translator
  • Moore machines
  • mealy machines
  • composite machine
  • Conversion from Mealy to Moore
  • Conversion from Moore to 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
  • Ardenb4s 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
  • conversion of automata machine to grammar 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 PDA
  • non-deterministic PDA
  • conversion of PDA into context free grammar
  • conversion of context free grammar into PDA and vice versa
  • CFG equivalent to PDA
  • Petrinet model
5
Unit 5

Turing Machine

  • Techniques for construction of Turing Machine
  • Universal Turing machine
  • Multitape Turing machine
  • multihead Turing machine
  • multidimensional Turing machine
  • N-P complete problems
  • Decidability and Recursively Enumerable Languages
  • 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 1b4s and 0b4s.
  • Design a program for creating a machine which count number of 1b4s and 0b4s in a given string.
  • Design a Program to find 2b4s 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 thatb4s accepts the following language anbncn where n>0

Reference Books

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