SGBAU SY Computer Engg syllabus

SGBAU · Second Year B.E. Computer Engineering · NEP 2020

Theory of Computation

4KE211PC · 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).

All notes for this subject
  1. Unit 1: Finite State Machines

    7 hours

    Alphabets, 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

  2. Unit 2: Regular Expressions and Regular Grammars

    7 hours

    Regular 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

  3. Unit 3: Context-Free Grammars and Languages

    7 hours

    Grammars 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

  4. Unit 4: Pushdown Automata

    7 hours

    Defining 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

  5. Unit 5: Turing Machines

    7 hours

    The 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

  6. Unit 6: Decidability and Undecidability

    7 hours

    Decidable 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

Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).