PAHSU · Second Year B.Tech. Computer Science and Engineering · NEP 2020
Theory of Computation
CSEPCC-05 · Semester IV · 3 credits · ISE 30 + ESE 70
2 lecture credits and 1 tutorial credit; the tutorial adds ICA 25.
Unit 1: Regular Expressions
6 hoursRegular expressions and the corresponding regular languages, with examples and applications; unions, intersections and complements of regular languages.
Examined in the 70-mark end-semester paper
Unit 2: Finite Automata
10 hoursDefinition and representation of finite automata; non-deterministic FA and NFA with null transitions; equivalence of DFA and NFA; Kleene's theorem; minimising the number of states; Moore and Mealy machines.
Examined in the 70-mark end-semester paper
Unit 3: Grammars and Languages
7 hoursTypes of grammars and languages, derivation trees and ambiguity; Chomsky normal form; union, concatenation and closure of CFLs; eliminating null and unit productions and useless variables.
Examined in the 70-mark end-semester paper
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Chomsky hierarchy and applications of CFGs
Unit 4: Pushdown Automata
6 hoursDefinition, deterministic PDA and types of acceptance; equivalence of CFGs and PDAs.
Examined in the 70-mark end-semester paper
- Pushdown automata
- PDA acceptance: final state and empty stack
- Deterministic and nondeterministic PDA
- Equivalence of PDA and CFG
Unit 5: CFLs and Non-CFLs
5 hoursThe pumping lemma for context-free languages with examples; intersections and complements of CFLs.
Examined in the 70-mark end-semester paper
Unit 6: Turing Machines
7 hoursModels of computation; Turing machines as language acceptors; combining Turing machines.
Examined in the 70-mark end-semester paper
Unit 7: Variations of Turing Machines
4 hoursTuring machines with doubly infinite tapes, multitape and non-deterministic Turing machines, and the universal Turing machine.
Examined in the 70-mark end-semester paper
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).