UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2025 Examination

GTU 2160704 Theory of Computation (TOC) Summer 2025 Paper Solution & PDF

B.E. · Computer Engineering · Semester 6 · Subject Code: 2160704
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours10:30 AM – 1:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Show that (𝑝 → ¬ 𝑝) 𝘝 (¬ 𝑝 → 𝑝) is a tautology.
3 Marks
(b)
Prove that for any; 𝑛 ≥ 4, 𝑛! > 2𝑛.
4 Marks
(c)

Explain the concept of “Language” and discuss how FA, which accepts or rejects a language, is constructed using a regular expression.

7 Marks

Question 2

14 MarksMedium
(a)
Define: Context Free Language.
3 Marks
(b)
Write only the algorithmic steps to minimize a given finite automata.
4 Marks
(c)

Apply the rules to convert NFA to FA and create a minimum state FA for the given NFA here.

7 Marks
OR OPTION
(c)

Apply pumping lemma for regular languages and prove that the language of palindromes is not regular.

7 Marks

Question 3

14 MarksMedium
(a)
Apply the rules and draw NFA – λ for ((0)* + (1)*) (00)*(1)
3 Marks
(b)
Apply the rules to construct NPDA for accepting a palindrome.
4 Marks
(c)

Apply the rules and convert regular expression to regular grammar for the given regular expression. (011 + 1)* (01)*

7 Marks
OR OPTION
(a)

Apply the rules to find λ - closure of set of states for the given NFA- λ and find λ(A), λ(B), λ(C) and λ(D). 𝒒 𝜹(𝒒, 𝝀) 𝜹(𝒒, 𝟎) 𝜹(𝒒, 𝟏) A {B} {A} ∅ B {D} {C} ∅ C ∅ ∅ {B} D ∅ {D} ∅

3 Marks
(b)
Explain Context Free Languages.
4 Marks
(c)
Apply the method to check if the given grammar is unambiguous or not:
expr → expr + expr | expr * expr | (expr) | d
7 Marks

Question 4

14 MarksMedium
(a)
Why is the “Pushdown” automata called “push-down” automata?
3 Marks
(b)

Given a regular expression, you can always create a PDA for it. Explain the statement.

4 Marks
(c)
Apply the rules and draw the TM for the language of odd palindromes.
7 Marks
OR OPTION
(a)
The FA is more powerful than DPDA. Explain if True or False?
3 Marks
(b)
Discuss the pumping lemma for CFL.
4 Marks
(c)

Apply the rules and draw the TM to accept the language L = {ab}*{aba} over Σ = {a,b}*

7 Marks

Question 5

14 MarksMedium
(a)
Define decidability of a language.
3 Marks
(b)
Discuss Chomsky hierarchy.
4 Marks
(c)
Discuss Primitive Recursive Functions.
7 Marks
OR OPTION
(a)
What is a post correspondence problem?
3 Marks
(b)
Discuss Church-Turing thesis.
4 Marks
(c)
Show how all computable functions are 𝜇 -recursive.
7 Marks
College Exam Groups

Studying for Theory of Computation?

Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions for Theory of Computation (TOC) (Summer 2025, B.E. · Computer Engineering, Sem 6). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.

Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.

Download PDF