PAHSU SY AI&DS syllabus

PAHSU · Second Year B.Tech. Artificial Intelligence and Data Science · NEP 2020

Theory of Computation

ADPCC-05 · Semester IV · 3 credits · ISE 30 + ESE 70

  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

    • Alphabets, strings and languages
    • Regular expressions and identities
    • Closure properties of regular languages
  2. Unit 2: Finite Automata

    10 hours

    Finite automata: definition and representation; nondeterministic FA and NFA with Λ-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 star of CFLs; eliminating Λ-productions, unit productions and useless variables from a CFG.

    Examined in the 70-mark end-semester paper

    • Chomsky hierarchy
    • Derivation trees, sentential forms and ambiguity
    • Simplification of CFGs
    • Chomsky and Greibach normal forms
  4. Unit 4: Pushdown Automata

    6 hours

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

    Examined in the 70-mark end-semester paper

    • Pushdown automata and acceptance
    • Deterministic pushdown automata
    • Equivalence of CFG and PDA
  5. Unit 5: Context-Free and Non-Context-Free Languages

    5 hours

    The pumping lemma for CFLs 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; the Turing machine as a language acceptor; combining Turing machines.

    Examined in the 70-mark end-semester paper

    • Church–Turing thesis
    • Turing machines and their design
    • Recursive and recursively enumerable languages
  7. Unit 7: Variations in Turing Machines

    4 hours

    TMs with doubly infinite tapes, multitape and nondeterministic TMs, the universal TM; undecidability; time- and space-bounded computation.

    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).