Skip to content
EndsemMay 20252019 patternTE IT

Theory of Computation (TOC) SPPU Endsem Question Paper May 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
May 2025
Max. marks
70
Time
2½ Hours
Semester
V
Paper code
[6403]-120

Printed for: T.E (Information Technology)

Instructions to the candidates

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

Questions

  1. Q1

    1. a)

      Construct CFG for the language L which consists of strings over {0,1}* with at least one occurrence of “000”.

      [4]
    2. b)

      Explain any three closure properties of Context Free language.

      Also asked:May 2024

      [6]
    3. c)

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

      [8]

  2. Q2

    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.

      [6]
    3. c)

      Explain Chomsky Hierarchy of grammar. 2

      Also asked:Nov 2025

      [4]

  3. Q3

    1. a)

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

      [6]
    2. b)

      Write formal definitions of i) Deterministic PDA ii) Non-deterministic PDA

      [4]
    3. c)

      Define post machine. Design PM to check well formedness of parentheses.

      [7]

  4. Q4

    1. a)

      Compare finite automata and push down automata.

      [4]
    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 2024 ·Nov 2022

      [7]

  5. Q5

    1. a)

      Explain the power of Turing machine over Finite Automata.

      Also asked:Nov 2025

      [4]
    2. b)

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

      [8]
    3. c)

      Explain Halting Problem of Turing Machine.

      [6]

  6. Q6

    1. a)

      Write a note on variants of Turing machine.

      [8]
    2. b)

      Explain solvable problems and unsolvable problems.

      [4]
    3. c)

      Construct a Turing machine for 1’s complement of a binary number.

      Also asked:Nov 2022

      [6]

  7. Q7

    1. a)

      Show that for two recursive languages L1 and L2, each of the following are recursive. i) L1  L2 ii) L1  L2

      [9]
    2. b)

      Write a note on Node-Cover Problem.

      [8]

  8. Q8

    1. a)

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

      [8]
    2. b)

      Define P-class problems and NP- class problems. Explain them with suitable examples. … … …

      [9]