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.
Unit 1: Regular Languages and Finite Automata
6 hoursProofs 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
- Alphabets, strings and languages
- Regular expressions and identities
- Deterministic finite automata
- Closure properties of regular languages
Unit 2: Nondeterminism and Kleene's Theorem
7 hoursNFAs 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
Unit 3: Context-Free Grammars
8 hoursDefinition; 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
Unit 4: Parsing and Pushdown Automata
7 hoursPushdown 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
Unit 5: Context-Free Languages
7 hoursCFLs 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
Unit 6: Turing Machines
7 hoursTuring 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.