Skip to content
EndsemMay 20242019 patternTE IT

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 PDFMost repeated TOC questions
Subject code
314441
Pattern
2019 pattern
Exam
Endsem
Session
May 2024
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[6262]-121

Printed for: T.E.(Information Technology 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 marks.
  4. Assume suitable data, if necessary.

Questions

  1. Q1

    1. a)

      What is an ambiguous grammar? Explain with a suitable example.

      [4]
    2. b)

      What is Regular Grammar? Explain types of regular grammar.

      Also asked:Nov 2022

      [5]
    3. c)

      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)

      Explain any three closure properties of Context Free language.

      Also asked:May 2025

      [6]

  3. Q3

    1. a)

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

      Also asked:May 2025 ·Nov 2022

      [6]
    2. b)

      Write a note on Instantaneous Description of PDA with an example 2

      [5]
    3. c)

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

      [6]

  4. Q4

    1. a)

      Compare Finite Automata and Pushdown Automata.

      Also asked:Nov 2022

      [4]
    2. b)

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

      [7]
    3. c)

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

      [6]

  5. Q5

    1. a)

      Write a note on Universal turing Machine

      Also asked:Nov 2025 ·Nov 2022

      [6]
    2. b)

      Explain Church Turing hypothesis.

      [3]
    3. c)

      Define Turing machine and design a right shifting TM over alphabet {0,1} with an example.

      [9]

  6. Q6

    1. a)

      Construct a Turing Machine to replace string ‘110’ by ‘101’ in a binary input string. Write down transition table along with diagram.

      [10]
    2. b)

      Discuss the following terms i) Post Correspondence Problem ii) Halting Problem of Turing Machine

      [8]

  7. Q7

    1. a)

      What do you mean by NP problems? Justify why the Travelling Salesman problem is a NP problem.

      [8]
    2. b)

      Define decidability of problem with suitable example. Describe un- decidable problems for context-free Grammar.

      [9]

  8. Q8

    1. a)

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

      Also asked:Nov 2025 ·Nov 2022

      [9]
    2. b)

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

      [8]