Skip to content
EndsemMay 20242019 patternTE Comp

Theory of Computation (TOC) SPPU Endsem Question Paper May 2024

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 2024
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[6262]-36

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 indicates 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.

      [8]
    2. b)

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

      [10]

  2. Q2

    1. a)

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

      [12]
    2. b)

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

      [6]

  3. Q3

    1. a)

      What is pushdown automata? Define PDA pictorially and mathematically with respect to input tape, stack, finite control and Instanteous description. Design a PDA for accepting a language {a n b 2n |n>=1}

      [8]
    2. b)

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

      [10]

  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)

      Elaborate the following terms with proper examples i) Universal Turing Machine (UTM) ii) Recursively Enumerable Languages

      Also asked:May 2023

      [4]
    2. b)

      Design a TM that multiplies two unary numbers over  = {1}. Write simulation for the string 11*111.

      [7]
    3. c)

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

      [6]

  6. Q6

    1. a)

      Construct a TM for substraction of two unary numbers f(a-b) = c where a is always greater than b.

      [5]
    2. b)

      What is undecidability? How do we prove universal language is undecidable? What is the relation between undecidability and reducibility theory. 4

      [12]

  7. Q7

    1. a)

      What do you mean by polynomial time reduction? Explain with an example of SAT.

      Also asked:May 2023

      [7]
    2. b)

      Explain the following terms with respect to computations complexity with example. i) Solvable Vs Unsolvable problem ii) Decidable Vs. Undecidable problem iii) P Vs NP problem

      [10]

  8. Q8

    1. a)

      Explain in brief the term “recursively enumerable”.

      [6]
    2. b)

      Explain examples of problems in NP.

      [6]
    3. c)

      Differentiate between P class and NP class. 

      [5]