Search your topic here

TOC



THEORY OF COMPUTATION

Unit-I

  • Introduction of Automata Theory: 
  • Examples of automata machines, 
  • Finite Automata as a language acceptor and translator, 
  • Moore machines and mealy machines, 
  • composite machine, 
  • Conversion from Mealy to Moore and vice versa.


Unit-II

  • 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 and closure, 
  • 2 way DFA.


Unit-III

  • Grammars: 
  • Types of grammar, 
  • context sensitive grammar, 
  • and 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 and Greibach normal form.


Unit-IV

  • 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.


Unit-V

  • Turing Machine: Techniques for construction. 
  • Universal Turing machine Multitape, 
  • multihead and 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.

LEAVE A REPLY