RTMNU · Second Year B.Tech Artificial Intelligence & Data Science · NEP 2020
Theory of Computation
BAD4T13 · Semester IV · 4 credits · College 30 + university 70
A 4-credit course with a weekly tutorial.
Unit 1: Finite Automata
8 hoursAlphabets, sets and languages and the Chomsky hierarchy; DFAs, their transition diagrams and tables and languages; NFAs and their equivalence with DFAs; ε-transitions and their elimination; DFA minimisation; Moore and Mealy machines and their interconversion.
Examined in the 70-mark end-semester paper
- Alphabets, strings and languages
- Chomsky hierarchy
- Deterministic finite automata
- NFA and ε-NFA
- Equivalence of NFA and DFA
- Minimisation of DFA
- Moore and Mealy machines
Unit 2: Regular Expressions and Regular Grammars
7 hoursIdentities of regular expressions; converting DFAs to regular expressions and regular expressions to automata; regular, right-linear and left-linear grammars and their finite automata; the pumping lemma and closure properties of regular languages.
Examined in the 70-mark end-semester paper
- Regular expressions and identities
- Arden's theorem: FA to RE
- Converting RE to FA
- Regular grammars and finite automata
- Pumping lemma for regular languages
- Closure properties of regular languages
Unit 3: Context-Free Grammars
7 hoursDerivation trees and sentential forms, Chomsky and Greibach normal forms, ambiguity, minimisation of CFGs and the pumping lemma for context-free languages.
Examined in the 70-mark end-semester paper
- Derivation trees, sentential forms and ambiguity
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Pumping lemma for context-free languages
Unit 4: Pushdown Automata
7 hoursThe PDA model, acceptance of context-free languages by final state and by empty stack and their equivalence, and the equivalence of CFGs and PDAs.
Examined in the 70-mark end-semester paper
- Pushdown automata and acceptance
- Equivalence of CFG and PDA
Unit 5: Turing Machines and Decidability
7 hoursThe Turing machine model and design, the universal Turing machine, computable functions, linear bounded automata and context-sensitive languages, recursive and recursively enumerable languages, the halting problem, the Post correspondence problem and Church's hypothesis.
Examined in the 70-mark end-semester paper
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Linear bounded automata and context-sensitive languages
- Recursive and recursively enumerable languages
- Decidability and the halting problem
- Post correspondence problem
- Church–Turing thesis
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).