Theory of Computation


In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory and language, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?

Automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines. These abstract machines are called automata. Automata comes from the Greek word (Αυτόματα) which means that something is doing something by itself. Automata theory is also closely related to formal language theory,[5] as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set. Automata are used as theoretical models for computing machines, and are used for proofs about computability.

Grammar Languages Automaton Production Rules
Type - 0 Recursively enumerable Turing machine α → β (No Restriction)
Type - 1 Context-sensitive Linear-bounded non-deterministic Turing machine α A β → α γ β
Type - 2 Context-free Non-deterministic pushdown automaton A → γ
Type - 3 Regular Finite state automaton A → a and A → aB


Some of the applications of theory of computation is listed here:

  • Progrmming Language
  • Compiler
  • Interpreter
  • Editor
  • Computer
  • Language Beautifier
  • Scanning
  • Parsing

Academic Year: 2016-17

Course Detail

Syllabus for Internal Test:

Review of Mathematical Theory: Sets, Functions, Logical statements, Proofs, relations, languages, Mathematical induction, strong principle, Recursive definitions

Regular Languages and Finite Automata: Regular expressions, regular languages, Finite automata, Union, intersection and complement of regular languages. Non Determinism Finite Automata, Conversion from NFA to FA, elsilon - NFA, Conversion of -NFA to NFA and equivalence of three Kleene’s Theorem, Minimization of Finite automata Regular And Non Regular Languages – pumping lemma.

Context Free Grammar (CFG):Definition, Unions Concatenations And Kleen’s of Context free language Regular grammar, Derivations and Languages, Relationship between derivation and derivation trees

Web Resources: