GUG · Second Year B.Tech. Computer Science and Engineering · NEP 2020
Theory of Computation
STPCCCSE405 · Semester IV · 4 credits · IE 10 + mid-semester 10 + ESE 80
4 credits: 3 lectures and 1 tutorial a week.
Unit 1: Finite Automata
9 hoursThe Chomsky hierarchy; design of finite state machines and the acceptance of strings and languages; deterministic and non-deterministic finite automata and their equivalence; NFA with ε-transitions; minimisation of finite automata.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
Unit 2: Regular Languages and Context-Free Grammars
9 hoursRegular sets and expressions and their manipulation; equivalence of regular expressions and finite automata; the pumping lemma and closure properties of regular sets; conversion between regular expressions and regular grammars. Context-free grammars, derivation and parse trees, ambiguity and context-free languages; Chomsky and Greibach normal forms.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- 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
- Context-free grammars and derivations
- Ambiguous grammars
- Chomsky and Greibach normal forms
Unit 3: Pushdown Automata
9 hoursDefinition and model of the pushdown automaton; acceptance of CFLs by empty stack and by final state; equivalence of CFLs and PDAs and conversion between them; closure properties of CFLs; DPDA and NPDA; linear bounded automata and context-sensitive languages.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Pushdown automata
- PDA acceptance: final state and empty stack
- Equivalence of PDA and CFG
- Deterministic and nondeterministic PDA
- Context-sensitive languages and linear bounded automata
Unit 4: Turing Machines
9 hoursDefinition and model of the Turing machine and its design; computable functions; recursive and recursively enumerable languages and their properties; Church's hypothesis; types of Turing machine; the universal Turing machine.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Turing machines
- Designing Turing machines
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
- Recursive and recursively enumerable languages
Unit 5: Undecidability and Recursive Function Theory
9 hoursUndecidable problems about recursively enumerable languages and Turing machines; the Post correspondence problem; recursive function theory: basic functions and operations on them; the Ackermann function.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Decidability and the halting problem
- Post correspondence problem
- Primitive recursive and μ-recursive functions
Unit contents are summarised from the official GUG syllabus . AiCanCode.org is not affiliated with Gondwana University, Gadchiroli.