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.
Unit 1: Introduction to Automata Theory
7 hoursCentral 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
Unit 2: Nondeterministic Automata and Kleene's Theorem
6 hoursNFAs 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
- Nondeterministic finite automata and NFA to DFA conversion
- Conversions between regular expressions and finite automata
- Minimisation of DFA
- Role of the lexical analyser and input buffering
Unit 3: Context-Free Grammars
5 hoursUnion, 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
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Left recursion and left factoring
Unit 4: Pushdown Automata
7 hoursPushdown 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
- Pushdown automata
- Equivalence of PDA and CFG
- Top-down parsing: recursive descent and LL(1)
- Bottom-up parsing and shift-reduce
Unit 5: Context-Free Languages
7 hoursProperties 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
Unit 6: Turing Machines
7 hoursTuring 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
- Turing machines
- Designing Turing machines
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
Unit contents are summarised from the official SUK syllabus . AiCanCode.org is not affiliated with Shivaji University, Kolhapur.