RTMNU · Third Year B.Tech Computer Science & Engineering · NEP 2020
Theory of Computation
BCSE5T17 · Semester V · 2 credits · College 30 + university 70
2 credits (2 lecture hours a week).
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
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
- Conversions between regular expressions and finite automata
- Pumping lemma for regular languages
- Closure and decision properties of regular languages
- Regular grammars and their equivalence with FA
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
- Chomsky and Greibach normal forms
- Pushdown automata
- PDA acceptance: final state and empty stack
- Equivalence of PDA and CFG
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
- Designing Turing machines
- Universal Turing machine and the Church–Turing thesis
- Variants of Turing machines
- 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).