GUG SY CSE syllabus

GUG · Second Year B.Tech. Computer Science and Engineering · NEP 2020

Theory of Computation

STPCCCSE405 · Semester IV · 4 credits · IE 10 + mid-semester 10 + ESE 80

4 credits: 3 lectures and 1 tutorial a week.

All notes for this subject
  1. Unit 1: Finite Automata

    9 hours

    The Chomsky hierarchy; design of finite state machines and the acceptance of strings and languages; deterministic and non-deterministic finite automata and their equivalence; NFA with ε-transitions; minimisation of finite automata.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  2. Unit 2: Regular Languages and Context-Free Grammars

    9 hours

    Regular sets and expressions and their manipulation; equivalence of regular expressions and finite automata; the pumping lemma and closure properties of regular sets; conversion between regular expressions and regular grammars. Context-free grammars, derivation and parse trees, ambiguity and context-free languages; Chomsky and Greibach normal forms.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  3. Unit 3: Pushdown Automata

    9 hours

    Definition and model of the pushdown automaton; acceptance of CFLs by empty stack and by final state; equivalence of CFLs and PDAs and conversion between them; closure properties of CFLs; DPDA and NPDA; linear bounded automata and context-sensitive languages.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  4. Unit 4: Turing Machines

    9 hours

    Definition and model of the Turing machine and its design; computable functions; recursive and recursively enumerable languages and their properties; Church's hypothesis; types of Turing machine; the universal Turing machine.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

  5. Unit 5: Undecidability and Recursive Function Theory

    9 hours

    Undecidable problems about recursively enumerable languages and Turing machines; the Post correspondence problem; recursive function theory: basic functions and operations on them; the Ackermann function.

    Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then

Unit contents are summarised from the official GUG syllabus . AiCanCode.org is not affiliated with Gondwana University, Gadchiroli.