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 :

Grammar Languages Automaton Production rules
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
Alan Turing Theory of Computation

Course Detail

Course Detail

Syllabus for Internal Examination

  • 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, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, ^-Non Determinism Finite Automata 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, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF
  • Pushdown Automata: CFL And NCFL: Definition, deterministic PDA, Equivalence of CFG and PDA, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL

GTU Question papers

2021-11-24 2021-01-27 2017-05-05 2017-05-03 2016-10-26 2016-10-25
2016-05-17 2016-05-11 2015-12-14 2015-05-14 2014-12-05 2014-05-28
2013-12-06 2013-06-03 2013-01-05 2012-05-17 2011-11-28 2011-05-21

Course Detail

Syllabus for Internal Examination

  • 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, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, ^-Non Determinism Finite Automata 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, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF
  • Pushdown Automata: CFL And NCFL: Definition, deterministic PDA, Equivalence of CFG and PDA, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL

Course Detail

Syllabus for Internal Examination

  • 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, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, ^-Non Determinism Finite Automata 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, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF

Course Detail

Syllabus for Internal Examination

  • 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, applications, Automata with output-Moore machine, Mealy machine, Finite automata, memory requirement in a recognizer, definition, union, intersection and complement of regular languages.Non Determinism Finite Automata, Conversion from NFA to FA, ^-Non Determinism Finite Automata 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, Ambiguity Unambiguous CFG and Algebraic Expressions BacosNaur Form (BNF), Normal Form – CNF

Video Resources

Web Resources