SGBAU · Second Year B.E. Computer Science and Engineering · NEP 2020
Theory of Computation
4CS211PC · Semester IV · 2 credits · IE 40 + ESE 60
The scheme gives it 2 credits for 3 lecture hours a week; it is examined like the 3-credit courses (40 + 60, 3 hours).
Unit 1: Finite State Machines
7 hoursAlphabets, strings and languages; designing DFAs and NFAs, converting NFAs (with and without ε-moves) to DFAs, minimising automata; Moore and Mealy machines and converting between them.
Examined in the 60-mark end-semester paper
Unit 2: Regular Expressions and Regular Grammars
7 hoursRegular expressions and their identities, building expressions for languages and languages from expressions, FA to RE by Arden's theorem and RE to FA, the pumping lemma and closure properties of regular languages, regular grammars and their equivalence with FA.
Examined in the 60-mark end-semester paper
- Regular expressions
- Conversions between regular expressions and finite automata
- Arden's theorem
- Pumping lemma for regular languages
- Closure and decision properties of regular languages
- Regular grammars and their equivalence with FA
Unit 3: Context-Free Grammars and Languages
7 hoursGrammars and notation, leftmost and rightmost derivations and derivation trees, constructing CFGs, the pumping lemma for CFLs, simplification, Chomsky and Greibach normal forms, and the Chomsky hierarchy.
Examined in the 60-mark end-semester paper
Unit 4: Pushdown Automata
7 hoursDefining and constructing PDAs, acceptance of CFLs, equivalence of CFLs and PDAs, deterministic CFLs and DPDAs, properties of CFLs, context-sensitive languages and linear bounded automata.
Examined in the 60-mark end-semester paper
- 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 5: Turing Machines
7 hoursThe formal definition and design of Turing machines, computable functions, Church's hypothesis, counter machines, and variants — multi-tape and universal Turing machines.
Examined in the 60-mark end-semester paper
- Turing machines
- Designing Turing machines
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
Unit 6: Decidability and Undecidability
7 hoursDecidable problems and the halting problem; recursively enumerable languages and the properties of recursive and non-recursive languages; the Post correspondence problem; an introduction to recursive function theory.
Examined in the 60-mark end-semester paper
- Decidability and the halting problem
- Recursive and recursively enumerable languages
- Post correspondence problem
Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).