Office of Academic Affairs
Indian Institute of Science Education and Research Bhopal

Electrical Engineering and Computer Science

ECS 307: Theory of Computation (4)

Learning Objectives:

This course introduces the fundamentals of formal languages, models of computation and computability. At the end of this course students will be able to construct finite state machines and the equivalent regular expressions, pushdown automata and the equivalent context free grammars and Turing machines.

Course Contents:

  1. Introduction: Motivation for studying theory of computation, a quick overview of the subject. Notion of formal language. Language membership problem, why this is taken as the central problem of the subject.
  2.  Finite automata and regular expressions: DFA, NFA (with and without transitions), their equivalence. Proof that for some languages NFAs can be exponentially more succinct than DFAs. Definition of regular expressions. Proof that FAs recognize, and regular expressions denote the same class of languages, viz., regular languages.
  3.  Properties of regular languages: Pumping lemma and its use to prove non-regularity of a language, closure properties of class of regular languages, decision properties: converting among representations, testing emptiness, etc. Minimization of DFAs, Myhill-Nerode theorem.
  4. Context-free grammars and languages: Derivation, parse trees. Language generated by a CFG. Eliminating useless symbols, -productions, unit productions. Chomsky normal form.
  5. Pushdown automata: Definition, instantaneous description as a snapshot of PDA computation, notion of acceptance for PDAs: acceptance by null states, and by empty stack; the equivalence of the two notions. Proof that CFGs generate the same class of languages that PDAs accept.
  6.  Properties of context-free languages: Pumping lemma for context-free languages and its use to prove a language to be not context-free. Closure properties of the class of context- free languages. CYK algorithm for CFL membership, testing emptiness of CFLs.
  7. Turing machines: Historical context, informal proofs of undecidability. Definition of TM, instantaneous description as a snapshot of TM computation, notion of acceptance. Robustness of the model: both natural generalizations and restrictions keep the class of languages accepted invariant. (Generalizations: multi-track, multi-tape, nondeterministic, etc. Restrictions: semi-infinite tape, counter machines). Church-Turing hypothesis.
  8.  Undecidability: Definitions of r.e. and recursive languages. Turing machine codes, the diagonalization language and proof that it is not r.e. Universal Turing machine. Universal language, its semi-decidability. Reducibility and its use in proving undecidability. Rices theorem. Undecidability of Posts correspondence problem.
  9. Intractability: Motivation for the notion. The class P as consensus class of tractable sets. Classes NP, co-NP. Polynomial time reductions. NP-completeness, NP-hardness. Cook- Levin theorem. Mention about boundary of tractability: 2SAT vs. 3SAT, 2D matching vs. 3D matching. Some NP-completeness proofs: vertex cover, clique, independent sets, Hamiltonian graphs, subset-sum, set cover.

Selected Readings

Previous Back to Course List Next
Office of Academic Affairs