RTMNU · Third Year B.Tech Information Technology · NEP 2020
Theory of Computation
BIT5T17 · Semester V · 2 credits · College 30 + university 70
The scheme gives it 2 credits (2 lecture hours a week); its course page lists 3 lecture hours.
Unit 1: Introduction
7 hoursStrings, alphabets, languages and their operations; finite-state machines and the finite-automaton model, acceptance of strings and languages; NFA, DFA, their equivalence and NFA-to-DFA conversion; minimisation of FSMs and equivalence of two FSMs; Moore and Mealy machines.
Examined in the 70-mark end-semester paper
- Strings, languages and finite automata
- Deterministic finite automata
- NFA and ε-NFA
- Converting NFA to DFA
- Minimisation of DFA
- Moore and Mealy machines
Unit 2: Regular Sets, Regular Expressions
8 hoursRegular sets and regular expressions, their identities and manipulation; equivalence of RE and FA and their inter-conversion; the pumping lemma and closure properties of regular sets; regular, right- and left-linear grammars, their equivalence with FA and 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 and derivation trees; Chomsky and Greibach normal forms; pushdown automata — definition, model and acceptance of CFLs; equivalence of CFLs and PDAs and their inter-conversion; properties of CFLs.
Examined in the 70-mark end-semester paper
- Context-free grammars and derivations
- Parse trees and ambiguity
- Chomsky and Greibach normal forms
- Pushdown automata and acceptance
- Equivalence of CFG and PDA
Unit 4: Turing Machine
7 hoursTuring machines — definition, model and design; the universal Turing machine and computable functions; recursively enumerable languages; Church's hypothesis; counter machines and types of TM; undecidability, the properties of recursive and recursively enumerable languages, the Post 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
Unit contents are summarised from the official RTMNU syllabus . AiCanCode.org is not affiliated with Rashtrasant Tukadoji Maharaj Nagpur University (RTMNU).