SPPU · Third Year Information Technology · 2024 Pattern
Theory of Computation
PCC-303-IT · Semester V · 3 credits · CCE 30 + end-semester 70
Unit 1: Finite Automata
9 hoursSymbols, 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)
- Strings, languages and finite automata
- Deterministic finite automata
- NFA and ε-NFA
- Converting NFA to DFA
- Minimisation of DFA
- Moore and Mealy machines
Unit 2: Regular Expressions and Languages
9 hoursRegular 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
Unit 3: Context-free Grammars and Languages
9 hoursGrammars 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)
- Chomsky hierarchy
- Regular grammars and finite automata
- Context-free grammars and derivations
- Parse trees and ambiguity
Unit 4: Pushdown Automata and Turing Machines
9 hoursPDA 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
Unit 5: Decidability and Computational Complexity
9 hoursDecidable 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)
- Decidability and the halting problem
- Pumping lemma for regular languages
- Pumping lemma for context-free languages
- P, NP and polynomial-time reduction
- NP-complete problems, SAT and Cook's theorem
- Approximation algorithms
Unit contents are summarised from the official SPPU syllabus . AiCanCode.org is not affiliated with Savitribai Phule Pune University.