SPPU TE IT syllabus

SPPU · Third Year Information Technology · 2024 Pattern

Theory of Computation

PCC-303-IT · Semester V · 3 credits · CCE 30 + end-semester 70

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

    9 hours

    Symbols, strings and languages; DFA, NFA and ε-NFA; converting ε-NFA to NFA and NFA to DFA; minimising and comparing automata; Moore and Mealy machines and their inter-conversion.

    Marks: 14 in the end-semester exam · CCE: Unit test (12 marks, Units 1 & 2)

  2. Unit 2: Regular Expressions and Languages

    9 hours

    Regular expressions, identities and equivalence; RE to FA by the direct method; FA to RE by Arden's theorem; closure properties and applications of regular languages.

    Marks: 14 in the end-semester exam · CCE: Unit test (12 marks, Units 1 & 2)

    • Regular expressions and identities
    • Converting RE to FA
    • Arden's theorem: FA to RE
    • Closure properties of regular languages
  3. Unit 3: Context-free Grammars and Languages

    9 hours

    Grammars and the Chomsky hierarchy; left- and right-linear grammars and their conversions to each other and to FA; CFGs, derivation and syntax trees, leftmost and rightmost derivations, ambiguity; membership and parsing.

    Marks: 14 in the end-semester exam · CCE: Assignments or case study (12 marks, Units 3 & 4)

  4. Unit 4: Pushdown Automata and Turing Machines

    9 hours

    PDA definition, instantaneous descriptions, acceptance by final state and empty stack, designing PDAs, CFG–PDA equivalence; Turing machines, their design, variants, multi-tape and universal machines.

    Marks: 14 in the end-semester exam · CCE: Assignments or case study (12 marks, Units 3 & 4)

    • Pushdown automata and acceptance
    • Designing pushdown automata
    • Equivalence of CFG and PDA
    • Turing machines and their design
    • Variants of Turing machines and the universal TM
  5. Unit 5: Decidability and Computational Complexity

    9 hours

    Decidable problems for regular and context-free languages, undecidability and the halting problem; pumping lemmas for regular and context-free languages; P and NP, reducibility, NP-complete and NP-hard problems, SAT and Cook's theorem, node cover; approximation algorithms.

    Marks: 14 in the end-semester exam · CCE: Seminar, open-book test or quiz (6 marks, Unit 5)

Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.