Skip to content
EndsemNov 20252019 patternTE IT

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

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 2025
Max. marks
70
Time
2½ Hours
Semester
V
Paper code
[6583]-127

Printed for: T.E. (Information Technology)

Instructions to the candidates

  1. Attempt Q.1 or Q.2, Q.3. or Q.4, Q.5 or Q.6, and Q.7 or Q.8.
  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)

      Write a formal definition of a Regular Grammar? Explain Chomsky Hierarchy of Grammar.

      Also asked:May 2025

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

  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)

      Write a short note on the Pumping Lemma for Context Free Language.

      [6]

  3. Q3

    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)

      Define the following terms with example. i) Pushdown Automata ii) Post Machine 3

      [6]

  4. Q4

    1. a)

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

      [6]
    2. b)

      Design a Post Machine which accepts the string with an equal number of a’s and b’s.

      [6]
    3. c)

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

      [6]

  5. Q5

    1. a)

      Construct a Turing Machine (TM) for checking if a set of parenthesis are well formed.

      [6]
    2. b)

      Write a short note on : i) Church-Turing thesis ii) Multi-tape TM

      [6]
    3. c)

      Explain the power of Turing Machine over Push Down Automata.

      Also asked:May 2025

      [5]

  6. Q6

    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)

      Write a short note on Universal Turing Machine.

      Also asked:May 2024 ·Nov 2022

      [5]

  7. Q7

    1. a)

      Write Short note on : i) Un-decidable Problem ii) Measuring Complexity

      Also asked:May 2024 ·Nov 2022

      [6]
    2. b)

      Let HALT TM ={where M is a TM and M halts on input w}. Prove that HALT TM is undecidable.

      [6]
    3. c)

      Define the following. i) NP Hard Problem ii) NP Complete Problem 4

      [5]

  8. Q8

    1. a)

      Prove that A DFA is a decidable language. A DFA ={ | B is a DFA that accepts input string w}.

      [6]
    2. b)

      Write a short note on Normal Forms of Boolean Expressions.

      [6]
    3. c)

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

      [5]