Skip to content

Theory of Computation (TOC) important questionsMost repeated in SPPU papers

These 9 questions appeared in more than one SPPU Theory of Computation paper we have: 6 papers, from Oct 2022 to Nov 2025. The most-asked come first. Each one links to the papers it was asked in.

All TOC papers and notes

Repeated questions

Endsem questions (9)

  1. 3×asked

    Write a short note on Universal Turing Machine.

    Nov 2025 ·May 2024 ·Nov 2022

  2. 3×asked

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

    Nov 2025 ·May 2024 ·Nov 2022

  3. 3×asked

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

    May 2025 ·May 2024 ·Nov 2022

  4. 2×asked

    Explain the power of Turing Machine over Push Down Automata.

    Nov 2025 ·May 2025

  5. 2×asked

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

    Nov 2025 ·May 2025

  6. 2×asked

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

    May 2025 ·Nov 2022

  7. 2×asked

    Explain any three closure properties of Context Free language.

    May 2025 ·May 2024

  8. 2×asked

    Compare Finite Automata and Pushdown Automata.

    May 2024 ·Nov 2022

  9. 2×asked

    What is Regular Grammar? Explain types of regular grammar.

    May 2024 ·Nov 2022

Questions count as repeated when their wording matches closely across papers. Numericals that depend on a figure are left out, since the figure changes from paper to paper.