Skip to content
EndsemNov 20222019 patternTE IT

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

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

Open the PDFMost repeated TOC questions
Subject code
314441
Pattern
2019 pattern
Exam
Endsem
Session
Nov 2022
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[5926]-119

Printed for: T.E. (Information Technology)

Instructions to the candidates

  1. Solve 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 indicate full marks.
  4. Assume suitable data, if necessary.

Questions

  1. Q1

    1. a)

      What is a Regular Grammar? Explain types of regular grammar.

      Also asked:May 2024

      [5]
    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.

      [7]

  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)

      Define Post machine.

      [3]
    2. b)

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

      [6]
    3. c)

      Define Push down Automata. Explain different types of PDA. Explain any two applications of PDA.

      Also asked:May 2025 ·May 2024

      [8]

  4. Q4

    1. a)

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

      [7]
    2. b)

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

      [6]
    3. c)

      Compare Finite Automata and Pushdown Automata.

      Also asked:May 2024

      [4]

  5. Q5

    1. a)

      Write a note on Universal turing Machine.

      Also asked:Nov 2025 ·May 2024

      [5]
    2. b)

      Explain post correspondance problem with a suitable example.

      [6]
    3. c)

      Construct a Turing machine to find 2’s complement of a binary number.

      Also asked:May 2025

      [7]

  6. Q6

    1. a)

      Design a Turing Machine to increment value of binary number by one.

      [8]
    2. b)

      Write short notes on i) Unsolvable problems ii) Applications of Turing Machine

      [6]
    3. c)

      What are recursive and recursively enumerable languages? 3

      [4]

  7. Q7

    1. a)

      What is a Traveling Salesman Problem? Justify that it is a NP-class problem.

      [8]
    2. b)

      Write short notes on i) A Simple Un-decidable problem ii) Measuring Complexity

      Also asked:Nov 2025 ·May 2024

      [9]

  8. Q8

    1. a)

      Explain Cook’s theorem in detail.

      [8]
    2. b)

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

      [9]