Skip to content
EndsemNov 20232019 patternTE Comp

Theory of Computation (TOC) SPPU Endsem Question Paper Nov 2023

All 8 questions from this SPPU endsem paper, as printed. Read them here or open the PDF.

Open the PDF
Subject code
310242
Pattern
2019 pattern
Exam
Endsem
Session
Nov 2023
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[6180]-46

Printed for: T.E. (Computer Engineering)

Instructions to the candidates

  1. Answer Q1 or Q2, Q3 or Q4, Q5 or Q6, Q7 or Q8.
  2. Neat diagrams must be drawn wherever necessary.
  3. Figures to the right side indicate full marks.
  4. Assume suitable data, if necessary.

Questions

  1. Q1

    1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [9]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [8]

  2. Q2

    1. a)

      S aB|bA A a|aS|bAA B b|bS|aBB    Derive using Leftmost Derivation and Rightmost Derivation: i) bbaaba ii) aaabbb. Draw parse tree for the same. 2

      [9]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [8]

  3. Q3

    1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [10]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [8]

  4. Q4

    1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
    3. c)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]

  5. Q5

    1. a)

      Design a Turing machine for well formed parenthesis.

      [6]
    2. b)

      Design a TM that accepts all strings over {1,0} with even number of 0 ’ s and even number of 1 ’ s.

      [8]
    3. c)

      Construct TM that recognizes language over alphabet 0,1 such that string ends in 10. 3

      [4]

  6. Q6

    1. a)

      Construct a TM to accept the language over {0,1} containing the substring 001.

      [6]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [8]
    3. c)

      Design Turing Machine for l ’ s Complement.

      [4]

  7. Q7

    1. a)

      What is post correspondence problem? Explain PCP with following instance of the set of the strings A and B.

      [8]
    2. b)

      State and explain with suitable example i) Decidable Problem ii) Undecidable Problem iii) Church-Turing Thesis.

      [9]

  8. Q8

    1. a)

      What is reducibility in Computability Theory ? Explain in detail, the polynomial - time reduction approach for proving that a problem is NP- Complete.

      [8]
    2. b)

      Explain with suitable example and diagrams i) Halting problem of TM ii) Multitape TM iii) Universal TM 

      [9]