PAHSU SY CSE syllabus

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.

All notes for this subject
  1. Unit 1: Regular Expressions

    6 hours

    Regular 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

  2. Unit 2: Finite Automata

    10 hours

    Definition 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

  3. Unit 3: Grammars and Languages

    7 hours

    Types 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

  4. Unit 4: Pushdown Automata

    6 hours

    Definition, deterministic PDA and types of acceptance; equivalence of CFGs and PDAs.

    Examined in the 70-mark end-semester paper

  5. Unit 5: CFLs and Non-CFLs

    5 hours

    The pumping lemma for context-free languages with examples; intersections and complements of CFLs.

    Examined in the 70-mark end-semester paper

  6. Unit 6: Turing Machines

    7 hours

    Models of computation; Turing machines as language acceptors; combining Turing machines.

    Examined in the 70-mark end-semester paper

  7. Unit 7: Variations of Turing Machines

    4 hours

    Turing machines with doubly infinite tapes, multitape and non-deterministic Turing machines, and the universal Turing machine.

    Examined in the 70-mark end-semester paper

Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).