Mumbai University SE IT syllabus

Mumbai University · Second Year Information Technology · NEP 2020

Automata Theory

2343114 · Semester III · 3 credits · Internal tests 40 + end-semester 60

End-semester paper (2 hours): Six questions of 15 marks; Q1 is compulsory and you answer four.

All notes for this subject
  1. Module 1: Introduction and Regular Languages

    5 hours

    Alphabets, strings and languages; regular expressions and languages; regular grammars, right and left linear; closure properties.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Strings, languages and finite automata
    • Regular expressions and identities
    • Regular grammars and finite automata
    • Closure properties of regular languages
  2. Module 2: Finite Automata

    9 hours

    FA as acceptors; NFA with and without ε; DFA; RE to NFA; NFA to DFA; reducing a DFA; FA to RE; Moore and Mealy machines and their conversion; limits of FA.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  3. Module 3: Context-free Grammars

    8 hours

    CFGs; leftmost and rightmost derivations; ambiguity; simplification; CNF and GNF; the Chomsky hierarchy.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  4. Module 4: Pushdown Automata

    5 hours

    Deterministic single-stack PDA; equivalence of PDA and CFG; power and limits of PDA.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Pushdown automata and acceptance
    • Designing pushdown automata
    • Equivalence of CFG and PDA
  5. Module 5: Turing Machines

    7 hours

    Deterministic TMs; variants of TMs; the halting problem; the power of TMs.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

  6. Module 6: Applications of Automata

    3 hours

    Applications of FA, CFG, PDA and TM; compilers and their phases.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Applications of automata
    • Compiler phases

Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.