SPPU TE Computer syllabus

SPPU · Third Year Computer Engineering · 2024 Pattern

Theory of Computation

PCC303COM · Semester V · 3 credits · CCE 30 + end-semester 70

All notes for this subject
  1. Unit 1: Introduction to Formal Languages and Finite Automata

    9 hours

    Strings, languages and operations on languages; DFA, NFA and ε-NFA, their conversions and DFA minimisation; 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

    RE operators, precedence and algebraic laws, Kleene's theorem; RE to NFA/DFA and DFA to RE with Arden's theorem; the pumping lemma; closure and decision properties; the Myhill–Nerode theorem.

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

  3. Unit 3: Context Free Grammars and Languages

    9 hours

    CFGs, derivations and parse trees, ambiguity; simplification (ε, unit and useless productions); Chomsky and Greibach normal forms; the pumping lemma for CFLs, closure properties, the Chomsky hierarchy and applications.

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

  4. Unit 4: Push Down Automata

    9 hours

    PDAs, acceptance by final state and empty stack, NPDA, equivalence of PDA and CFG, applications, the Post machine.

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

  5. Unit 5: Turing Machine and Computability Theory

    9 hours

    Turing machines, instantaneous descriptions and constructions; the universal TM and the Church–Turing thesis; decidability and the halting problem, reducibility; time and space measures, P, NP and NP-completeness.

    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.