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.
Module 1: Introduction and Regular Languages
5 hoursAlphabets, 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
Module 2: Finite Automata
9 hoursFA 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
- Deterministic finite automata
- NFA and ε-NFA
- Converting RE to FA
- Converting NFA to DFA
- Minimisation of DFA
- Arden's theorem: FA to RE
- Moore and Mealy machines
Module 3: Context-free Grammars
8 hoursCFGs; 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
- Context-free grammars and derivations
- Parse trees and ambiguity
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Chomsky hierarchy
Module 4: Pushdown Automata
5 hoursDeterministic 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
Module 5: Turing Machines
7 hoursDeterministic 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
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Decidability and the halting problem
Module 6: Applications of Automata
3 hoursApplications 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.