RTMNU · Third Year B.Tech Computer Science & Engineering (AI & ML) · NEP 2020
Theory of Computation
BCSEAI&ML5T17 · Semester V · 2 credits · College 30 + university 70
A 2-credit course.
Unit 1: Introduction
7 hoursStrings, alphabets, languages and their operations; finite state machines and the acceptance of strings and languages; NFA and DFA, their equivalence and conversion; minimisation and equivalence of FSMs; Moore and Mealy machines.
Examined in the 70-mark end-semester paper
- Alphabets, strings and languages
- Deterministic finite automata
- NFA and ε-NFA
- Equivalence of NFA and DFA
- Minimisation of DFA
- Moore and Mealy machines
Unit 2: Regular Sets, Regular Expressions
8 hoursRegular sets and expressions, identity rules and manipulation of regular expressions; equivalence and inter-conversion of RE and FA; the pumping lemma and closure properties of regular sets; regular, right-linear and left-linear grammars, their equivalence with FA and inter-conversion between RE and RG.
Examined in the 70-mark end-semester paper
- Regular expressions and identities
- Converting RE to FA
- Arden's theorem: FA to RE
- Pumping lemma for regular languages
- Closure properties of regular languages
- Regular grammars and finite automata
Unit 3: Context Free Grammar
7 hoursContext-free grammars, derivation trees, Chomsky and Greibach normal forms; pushdown automata, their model and acceptance of CFLs; equivalence and inter-conversion of CFLs and PDAs; properties of CFLs.
Examined in the 70-mark end-semester paper
- Derivation trees, sentential forms and ambiguity
- Chomsky and Greibach normal forms
- Pushdown automata and acceptance
- Equivalence of CFG and PDA
- Closure properties of context-free languages
Unit 4: Turing Machine and Undecidability
7 hoursThe Turing machine model and design, the universal Turing machine, computable functions, recursively enumerable languages, Church's hypothesis, counter machines and types of TMs; properties of recursive and recursively enumerable languages, Post's correspondence problem and an introduction to recursive function theory.
Examined in the 70-mark end-semester paper
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Church–Turing thesis
- Recursive and recursively enumerable languages
- Decidability and the halting problem
- Post correspondence problem
- Primitive recursive and μ-recursive functions
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).