Mumbai University · Second Year Computer Engineering · NEP 2020
Computational Theory
2114111 · Semester IV · 3 credits · Internal tests 40 + end-semester 60
End-semester paper (2 hours): Six questions of 20 marks; Q1 is compulsory and you answer three.
Module 1: Basic Concepts and Regular Languages
5 hoursAlphabets, strings and languages; regular operations and expressions; Arden's theorem; closure and decision properties; the pumping lemma for regular languages.
Examined in one of the two internal tests and in the 60-mark end-semester paper
Module 2: Finite Automata
6 hoursDFA and NFA as recognisers; ε-transitions; NFA to DFA; DFA minimisation; Moore and Mealy machines; applications and limits of FA.
Examined in one of the two internal tests and in the 60-mark end-semester paper
Module 3: Regular and Context-free Grammars
9 hoursGrammars and the Chomsky hierarchy; regular grammars, left and right linear grammars and their equivalence with FA; CFGs, derivations, parse trees and ambiguity; simplification; CNF and GNF; the pumping lemma and closure of CFLs.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Chomsky hierarchy and applications of CFGs
- Regular grammars and their equivalence with FA
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Pumping lemma for context-free languages
Module 4: Pushdown Automata
5 hoursPDA as generator, decider and acceptor; deterministic and nondeterministic PDA; equivalence of PDA and CFG; applications.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Pushdown automata
- PDA acceptance: final state and empty stack
- Deterministic and nondeterministic PDA
- Equivalence of PDA and CFG
Module 5: Turing Machines
7 hoursDesigning TMs as generators, deciders and acceptors; multitrack and multitape TMs; the universal TM; power and limits of TMs.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Turing machines
- Designing Turing machines
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
Module 6: Decidability and Computability
5 hoursDecidable and undecidable problems; recursive and recursively enumerable languages; the halting problem; Rice's theorem; the Post correspondence problem.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Decidability and the halting problem
- Recursive and recursively enumerable languages
- Rice's theorem
- Post correspondence problem
Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.