SUK SY CSE syllabus

SUK · Second Year B.Tech. Computer Science and Engineering · NEP 2020

Automata Theory

CSE2203 · Semester IV · 4 credits · ISE 10 + mid-semester 30 + ESE 60

3 lectures and 1 tutorial a week, 4 credits.

  1. Unit 1: Introduction to Automata Theory

    7 hours

    Central concepts of automata theory; recursive definitions; regular expressions and regular languages; deterministic and nondeterministic finite automata and the epsilon-NFA.

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

  2. Unit 2: Nondeterministic Automata and Kleene's Theorem

    6 hours

    NFAs with null transitions and the equivalence of finite automata; Kleene's theorem; minimal automata, NFA-to-DFA conversion and DFA minimisation; the role of the lexical analyser.

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

  3. Unit 3: Context-Free Grammars

    5 hours

    Union, concatenation and Kleene star of CFLs; derivations and parse trees; simplified normal forms; ambiguity and its elimination; eliminating left recursion and left factoring; the role of the parser.

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

  4. Unit 4: Pushdown Automata

    7 hours

    Pushdown automata and their properties; the equivalence of CFGs and PDAs; top-down and bottom-up parsing with PDAs; applications.

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

  5. Unit 5: Context-Free Languages

    7 hours

    Properties and applications of context-free languages; non-context-free languages; the pumping lemma for context-free languages.

    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 and for computing partial functions; combining Turing machines; multi-tape and universal Turing machines.

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

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