UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2025 Examination

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

B.E. · Computer Engineering · Semester 6 · Subject Code: 3160704
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)

Differentiate between constructive proofs and proofs using contradiction with examples.

3 Marks
(b)

Write the Strong Principle of Mathematical Induction and prove that for any integer 𝑛 ≥ 2, 𝑛 is either a prime or a product of two or more primes.

4 Marks
(c)
Explain the importance of distinguishable strings and equivalent classes’ w.r.t.

regular languages.

7 Marks

Question 2

14 MarksMedium
(a)
Define Pushdown Automata.
3 Marks
(b)
Explain the idea of Finite State Machines with examples.
4 Marks
(c)

Apply the subset construction technique and draw the FA accepting the same language represented by given NFA.

7 Marks
OR OPTION
(c)
Convert the given regular expression to its equivalent NFA-λ.

𝑟 = 1 + (101)∗ 0 + 01 (01)∗ + 11(101)∗ + 00(11)∗

7 Marks

Question 3

14 MarksMedium
(a)

Construct a Finite Automata that accepts all strings over {0,1}∗ NOT containing the sub-string 101.

3 Marks
(b)
Show what languages are generate by the given context free grammar in each case.
1𝑆 → 𝑎𝑆𝑏 | 𝑏𝑆𝑎 |
2𝑆 → 𝑆𝑆 | 𝑏𝑆 | 𝑎
4 Marks
(c)
Construct the CFG for the language 𝐿 = {𝑥 ∈ {0,1}∗ | 𝑛0(𝑥) ≠ 𝑛1(𝑥)}.
7 Marks
OR OPTION
(a)
Show that the language pal of palindrome is not regular.
3 Marks
(b)

Find CFG generating the language of even-length strings in {𝑎, 𝑏}∗ with the two middle symbols equal.

4 Marks
(c)
Apply the rules and show step by step conversion of the following grammar to CNF.
𝑆 → 𝐴𝐵𝐶𝐵𝐶𝐷𝐴
𝐴 → 𝐶𝐷
𝐵 → 𝐶𝑏
𝐶 → 𝑎 | 𝛬
𝐷 → 𝑏𝐷 | 𝛬
7 Marks

Question 4

14 MarksMedium
(a)
Explain the pumping lemma for context free languages.
3 Marks
(b)

Explain unambiguous grammar with an example of converting ambiguous grammar to unambiguous.

4 Marks
(c)
Apply the rules and step by step create a Turing Machine to accept {𝑎, 𝑏}∗{𝑎𝑏𝑎}
7 Marks
OR OPTION
(a)
Explain Ogden’s Lemma.
3 Marks
(b)
Discuss the decision problems involving CFL.
4 Marks
(c)
Construct a Turing machine to accept the strings 𝑥. 𝑥𝑟𝑒𝑣
7 Marks

Question 5

14 MarksMedium
(a)
Explain the halting problem?
3 Marks
(b)
Discuss the Chomsky hierarchy.
4 Marks
(c)
Define and explain the working of Turing Machines.
7 Marks
OR OPTION
(a)

Explain the difference between decidability and acceptability of a language with respect to TM?

3 Marks
(b)

Explain Context-Sensitive Grammars and give example of a context-sensitive language.

4 Marks
(c)
Discuss the summary of Church – Turing thesis.
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