RTMNU · Third Year B.Tech Artificial Intelligence · NEP 2020
Theory of Computation
BAI6T21 · Semester VI · 3 credits · College 30 + university 70
Only Unit 2 prints its hours.
Unit 1: Finite Automata and Regular Expressions
Alphabets, strings and languages; deterministic and non-deterministic finite automata and their equivalence; regular expressions, conversion between regular expressions and finite automata, and applications of regular languages.
Examined in the 70-mark end-semester paper
- Alphabets, strings and languages
- Deterministic finite automata
- NFA and ε-NFA
- Equivalence of NFA and DFA
- Regular expressions and identities
- Converting RE to FA
Unit 2: Properties of Regular Languages
8 hoursThe pumping lemma for regular languages, closure properties, minimisation of DFA and the Myhill–Nerode theorem (basic idea).
Examined in the 70-mark end-semester paper
- Pumping lemma for regular languages
- Closure properties of regular languages
- Minimisation of DFA
Unit 3: Context-Free Grammars
Context-free grammars, derivations and parse trees, ambiguity, simplification of CFGs, and the Chomsky and Greibach normal forms.
Examined in the 70-mark end-semester paper
- Derivation trees, sentential forms and ambiguity
- Simplification of CFGs
- Chomsky and Greibach normal forms
Unit 4: Pushdown Automata
Definition and working of PDAs, their types, equivalence of PDAs and CFGs, acceptance by final state and empty stack, and applications of PDAs.
Examined in the 70-mark end-semester paper
- Pushdown automata and acceptance
- Equivalence of CFG and PDA
Unit 5: Turing Machines, Decidability and Complexity
The Turing machine model, designing Turing machines, their variants, the Church–Turing thesis, decidability and undecidability, and an introduction to complexity (P and NP, basic idea).
Examined in the 70-mark end-semester paper
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Church–Turing thesis
- Decidability and the halting problem
- P, NP and NP-complete problems
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).