Theory of Computation
Machines are frequently used as theoretical models for computing. In theoretical computer science and mathematics, the theory of computation is the branch of theoretical computer science 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 languages, 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, 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.
Formal languages are classified as follow :
|Type 0||Recursively enumerable||Turing machine||α → β|
|Type 1||Context-sensitive||Linear-bounded NDTM||αAβ → αγβ|
|Type 2||Context-free||NDPDA||A → γ|
|Type 3||Regular||Finite Automata||A → a , A → aB|
Syllabus for Internal Examination