RTMNU · Second Year B.Tech Computer Science & Engineering (Data Science) · NEP 2020
Theory of Computation
BCSE4T13 · Semester IV · 3 credits · College 30 + university 70
Unit 1: Finite State Machines
Strings, alphabets and language operations; finite automata and the acceptance of strings and languages; NFA and DFA, their equivalence and conversion; minimisation and equivalence of finite state machines; 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 and Regular Grammars
Regular sets and regular expressions, identity rules and manipulation of regular expressions; equivalence of RE and FA and their inter-conversion; the pumping lemma and closure properties of regular sets; the Chomsky hierarchy; right- 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
- Chomsky hierarchy
- Regular grammars and finite automata
Unit 3: Context-Free Grammars and Pushdown Automata
Context-free grammars and derivation trees, Chomsky and Greibach normal forms; pushdown automata and acceptance of CFLs, equivalence of CFLs and PDAs and their inter-conversion; closure properties and the pumping lemma for CFLs; an introduction to DCFLs and DPDAs.
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
- Pumping lemma for context-free languages
Unit 4: Turing Machines
The Turing machine model and the design of TMs, the universal Turing machine, computable functions, recursively enumerable languages and types of TMs; linear bounded automata and context-sensitive languages; counter machines.
Examined in the 70-mark end-semester paper
- Turing machines and their design
- Variants of Turing machines and the universal TM
- Recursive and recursively enumerable languages
- Linear bounded automata and context-sensitive languages
Unit 5: Decidability and Recursive Functions
Decidable and undecidable problems, properties of recursive and recursively enumerable languages, the halting problem, Post's correspondence problem, the Ackermann function and Church's hypothesis; basic and primitive recursive functions, bounded and unbounded minimalisation, μ-recursive functions and their equivalence with Turing-computable functions.
Examined in the 70-mark end-semester paper
- Decidability and the halting problem
- Post correspondence problem
- Church–Turing thesis
- 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).