Gujarat Technological UniversitySummer 2025 examination

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

B.E. · Computer Engineering · Semester 6 · Subject code 3160704
Download official PDFView PDF here
Share with your class
Total
70 marks
To pass
23 marks (33%)
Duration
2.5 Hours 10:30 AM – 1:00 PM
Questions
5 with internal choice
No solutions on this paper yetNeed them for your exam? Ask once. Papers that students ask for are solved first, and we aim to add them within 24 hours.

6 of 25 questions on this paper were also asked in other years. 6 more are types of question GTU sets again with new data. Each is marked below with the years it appeared.See all 34 repeated 3160704 questions, most asked first

Q.1

14 Marks
(a)
3 marks

Differentiate between constructive proofs and proofs using contradiction with examples.

(b)
4 marks

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.

(c)
7 marksAsked in 2 of 7 papers
Explain the importance of distinguishable strings and equivalent classes’ w.r.t.

regular languages.

Also asked in Summer 2023 Q1c

Q.2

14 Marks
(a)
3 marksAsked in 5 of 7 papers
Define Pushdown Automata.

Also asked in Winter 2025 Q4b OR, Winter 2024 Q3a, Winter 2023 Q4a OR, Summer 2023 Q4a

(b)
4 marks
Explain the idea of Finite State Machines with examples.
(c)
7 marksSame type asked in 3 of 7 papers

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

Also asked in Winter 2025 Q2c, Winter 2025 Q2c OR, Summer 2023 Q2c OR

(c)
7 marksSame type asked in 4 of 7 papers
Convert the given regular expression to its equivalent NFA-λ.

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

Also asked in Summer 2024 Q2c OR, Winter 2023 Q4b OR, Summer 2023 Q3a

Q.3

14 Marks
(a)
3 marksSame type asked in 4 of 7 papers

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

Also asked in Winter 2024 Q1c, Summer 2024 Q3a OR, Winter 2023 Q2c

(b)
4 marks
Show what languages are generate by the given context free grammar in each case.
1𝑆 → 𝑎𝑆𝑏 | 𝑏𝑆𝑎 |
2𝑆 → 𝑆𝑆 | 𝑏𝑆 | 𝑎
(c)
7 marksSame type asked in 5 of 7 papers
Construct the CFG for the language 𝐿 = {𝑥 ∈ {0,1}∗ | 𝑛0(𝑥) ≠ 𝑛1(𝑥)}.

Also asked in Summer 2026 Q3c, Winter 2025 Q2b, Winter 2024 Q4a, Winter 2023 Q3a

(a)
3 marks
Show that the language pal of palindrome is not regular.
(b)
4 marksSame type asked in 5 of 7 papers

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

Also asked in Summer 2026 Q3c, Winter 2025 Q2b, Winter 2024 Q4a, Winter 2023 Q3a

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

Also asked in Summer 2026 Q3c OR, Winter 2025 Q5c OR, Winter 2024 Q4c OR, Summer 2024 Q3c OR, Winter 2023 Q4c OR, Summer 2023 Q3c

Q.4

14 Marks
(a)
3 marksAsked in 4 of 7 papers
Explain the pumping lemma for context free languages.

Also asked in Winter 2025 Q4a, Winter 2023 Q4a, Summer 2023 Q3b

(b)
4 marks

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

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

Also asked in Summer 2024 Q4c OR

Q.5

14 Marks
(a)
3 marks
Explain the halting problem?
(b)
4 marksAsked in 2 of 7 papers
Discuss the Chomsky hierarchy.

Also asked in Winter 2023 Q5a OR

(c)
7 marks
Define and explain the working of Turing Machines.
(a)
3 marks

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

(b)
4 marks

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

(c)
7 marksAsked in 2 of 7 papers
Discuss the summary of Church – Turing thesis.

Also asked in Summer 2026 Q5b OR

More Theory of Computation papers

Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.

Summer 202670 marks · 5 questions
Winter 202570 marks · 5 questions
Winter 202470 marks · 5 questions
Summer 202470 marks · 5 questions

Other Semester 6 subjects

BE Computer

116AG01
Deep Learning and Neural Network
2160701
Software Engineering
2160704
Theory of Computation
2160707
Advanced Java

Preparing with friends?

Send this paper to your class group. Every question has its own link.

About this paper

Official Gujarat Technological University (GTU) examination paper 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 official PDF All Theory of Computation Papers (7) →Report a typo or correction
ViewDownload PDF