Skip to content
EndsemMay 20232019 patternTE Comp

Theory of Computation (TOC) SPPU Endsem Question Paper May 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
May 2023
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[6003]-347

Printed for: T.E. (Computer Engineering)

Instructions to the candidates

  1. Answer Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.
  2. Neat diagrams must be drawn wherever necessary.
  3. Figures to the right side indicate 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.

      [9]

  2. Q2

    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]

  3. Q3

    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]

  4. Q4

    1. a)

      What is NPDA? Construct a NPDA for the set of all strings over {a,b} with odd length palindrome.

      [9]
    2. b)

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

      [8]

  5. Q5

    1. a)

      Design a Turing Machine for the following language by considering transition table and diagram. i) TM that erases all non blank symbols on the tape where the sequence of non blank symbols does not contain any blank symbol B in between. ii) TM that find 2’s complement of a binary machine.

      [9]
    2. b)

      What is TM? Design TM to check well formedness of parenthesis. Expand the transition for (()) ()

      [9]

  6. Q6

    1. a)

      How turing machine can be use to compute the functions? Design turing machine for multiplication of two numbers.

      [9]
    2. b)

      Elaborate the following terms. i) Universal Turing Machine (UTM) ii) Recursively Enumerable Languages iii) Halting problem of Turing Machine

      Also asked:May 2024

      [9]

  7. Q7

    1. a)

      Define and Compare Class P and Class NP Problem with suitable diagram.

      [9]
    2. b)

      What do you mean by polynomial time reduction? Explain with suitable example.

      Also asked:May 2024

      [8]

  8. Q8

    1. a)

      Explain Satisfiability Problem and SAT Problem and comment on NP Completeness of the SAT Problem.

      [9]
    2. b)

      What makes a problem NP-Complete? How do we prove a problem is NP-complete? Are all decision problems NP-complete? 

      [8]