DBATU TY Computer syllabus

DBATU · Third Year B.Tech Computer Engineering · NEP 2020

Theory of Computations

26AF1245PC502 · Semester V · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60

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

    8 hours

    DFA and NFA, their languages and equivalence; applications; epsilon transitions and their elimination; minimising DFA; Moore and Mealy machines and their inter-conversion.

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

  2. Unit 2: Regular Expressions and Regular Grammars

    6 hours

    Identities of regular expressions; converting between DFA and regular expressions; regular grammars and finite automata; the pumping lemma and closure properties of regular languages.

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

  3. Unit 3: Context-Free Grammars

    6 hours

    Derivation trees, sentential forms and leftmost and rightmost derivations; ambiguity; minimising CFGs; CNF and GNF; the pumping lemma and properties of CFLs.

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

  4. Unit 4: Pushdown Automata and Turing Machines

    8 hours

    PDA model and acceptance by final state and by empty stack; equivalence of CFG and PDA; Turing machines, their languages, TMs as acceptors and as computers of integer functions; types of TMs.

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

  5. Unit 5: Recursive and Recursively Enumerable Languages

    6 hours

    Properties of recursive and r.e. languages; the universal TM; the halting problem and undecidable problems; context-sensitive languages and LBAs; the Chomsky hierarchy; decidability and the undecidability of PCP.

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

Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).