SPPU · Third Year Computer Engineering · 2024 Pattern
Theory of Computation
PCC303COM · Semester V · 3 credits · CCE 30 + end-semester 70
Unit 1: Introduction to Formal Languages and Finite Automata
9 hoursStrings, 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)
Unit 2: Regular Expressions and Languages
9 hoursRE 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)
Unit 3: Context Free Grammars and Languages
9 hoursCFGs, 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)
Unit 4: Push Down Automata
9 hoursPDAs, 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)
Unit 5: Turing Machine and Computability Theory
9 hoursTuring 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.