SUK TY CSE (DS) syllabus

SUK · Third Year B.Tech. Computer Science and Engineering (Data Science) · NEP 2020

Automata Theory

DS3104 · Elective I · Semester V · 3 credits · ISE 10 + mid-semester 30 + ESE 60

One of the Elective I options.

  1. Unit 1: Regular Languages and Finite Automata

    6 hours

    Proofs and recursive definitions; regular expressions and regular languages; finite automata; union, intersection and complement of regular languages; applications of FA.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

  2. Unit 2: Nondeterminism and Kleene's Theorem

    7 hours

    NFAs and NFAs with null transitions, equivalence of finite automata, Kleene's theorem (parts I and II) and minimal finite automata.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • NFA and ε-NFA
    • Equivalence of NFA and DFA
    • Converting RE to FA
    • Arden's theorem: FA to RE
    • Minimisation of DFA
  3. Unit 3: Context-Free Grammars

    8 hours

    Definition; union, concatenation and Kleene star of CFLs; derivation trees and ambiguity; simplified and normal forms.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Derivation trees, sentential forms and ambiguity
    • Closure properties of context-free languages
    • Simplification of CFGs
    • Chomsky and Greibach normal forms
  4. Unit 4: Parsing and Pushdown Automata

    7 hours

    Pushdown automata and deterministic PDAs; equivalence of CFGs and PDAs; top-down and bottom-up parsing.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Pushdown automata and acceptance
    • Deterministic pushdown automata
    • Equivalence of CFG and PDA
    • Top-down and predictive parsing
    • Shift-reduce parsing
  5. Unit 5: Context-Free Languages

    7 hours

    CFLs and non-CFLs, the pumping lemma, and intersections and complements of CFLs.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

  6. Unit 6: Turing Machines

    7 hours

    Turing machines as language acceptors, combining Turing machines, computing partial functions, multi-tape TMs and the universal TM.

    Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then

    • Turing machines and their design
    • Variants of Turing machines and the universal TM

Unit contents are summarised from the official SUK syllabus . AiCanCode.org is not affiliated with Shivaji University, Kolhapur.