Gujarat Technological UniversityWinter 2025 examination

GTU 3160704 Theory of Computation (TOC) Winter 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 2:30 PM – 5: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.

9 of 25 questions on this paper were also asked in other years. 12 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

Define - bijection. Let A = {1, 2, 3} and B = {a, b}. Check whether the function f = {(1, a), (2, b), (3, a)} is bijection or not? Justify your answer with reasons.

(b)
4 marksSame type asked in 2 of 7 papers

Define - Equivalence relation. Let A = {0, 1, 2, 3} and a relation R on A is defined as R = {(0, 0), (0,

1), (0,
3), (1, 0), (1,
1), (2,
2), (3, 0), (3,
3)}. Is R Reflexive? Symmetric? Transitive? Equivalence? Justify your answer in each case.

Also asked in Winter 2023 Q1b

(c)
7 marksSame type asked in 3 of 7 papers

Using the principle of mathematical induction, for all n > 0, prove that, {1 - (½)} {1 - (⅓)} {1 - (¼)} ….. {1 - (1/(n+1))} = 1/(n+1)

Also asked in Summer 2026 Q1c, Winter 2023 Q1c

Q.2

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

Convert the following Mealy machine into its equivalent Moore Machine:

Also asked in Summer 2026 Q2b

(b)
4 marksSame type asked in 5 of 7 papers
Find context-free grammars that generate the following languages:
i)L1 = {ai bj ck | i = j + k}
ii)L2 = {ai bj ck | j = i or j = k}

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

(c)
7 marksSame type asked in 3 of 7 papers

Using the subset construction method, convert the following NFA into its equivalent DFA accepting the same language.

Also asked in Summer 2025 Q2c, Summer 2023 Q2c OR

(c)
7 marksSame type asked in 3 of 7 papers

Using the subset construction method, convert the following NFA into its equivalent DFA accepting the same language.

Also asked in Summer 2025 Q2c, Summer 2023 Q2c OR

Q.3

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

Find a regular expression corresponding to each of the following subsets of {a, b}*:

i)The set of all the strings with length 5 exactly and next to last symbol is ‘b’
ii)The set of all strings that ends with sub-string ‘abb’
iii)The set of all strings having ‘a’ as the first symbol and ‘b’ as the last symbol

Also asked in Summer 2026 Q2a, Winter 2024 Q1b, Winter 2023 Q2b

(b)
4 marksSame type asked in 3 of 7 papers

Let M1 and M2 be the FAs accepting languages L1 and L2 respectively. Draw FAs accepting the L2 U L1 language.

Also asked in Summer 2026 Q3a, Winter 2023 Q2c OR

(c)
7 marksSame type asked in 3 of 7 papers

Find a minimum-state FA for the following FA that recognizes the same language.

Also asked in Summer 2026 Q2c, Winter 2023 Q3c OR

(a)
3 marksAsked in 2 of 7 papers
Discuss μ-recursive functions.

Also asked in Summer 2023 Q5c OR

(b)
4 marksAsked in 3 of 7 papers
Describe recursively enumerable languages and recursive languages.

Also asked in Winter 2024 Q5a OR, Summer 2023 Q5a OR

(c)
7 marksAsked in 4 of 7 papers

What is decidability? How to prove that the given language is undecidable? List some undecidable problems.

Also asked in Winter 2024 Q5a, Summer 2024 Q5a, Summer 2023 Q5a

Q.4

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

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

(b)
4 marks
Discuss two situations of Turing machine crashing with example.
(c)
7 marksAsked in 3 of 7 papers

Build a TM that accepts the language PALINDROME over {a, b}*. Also trace out the same on the input string abba.

Also asked in Summer 2026 Q5c OR, Winter 2023 Q5c

(a)
3 marksSame type asked in 3 of 7 papers

Decide whether the language L = {anbmambn | m, n ≥ 0} is a CFL or not and prove your answer.

Also asked in Summer 2026 Q4b OR, Summer 2024 Q3b OR

(b)
4 marksAsked in 5 of 7 papers
Define - Pushdown Automaton and acceptance by a PDA

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

(c)
7 marks

Draw Turing machine that accepts the language {anbncn | n ≥ 0} over {a, b, c}*. Also trace out the same on the input string aabbcc.

Q.5

14 Marks
(a)
3 marksAsked in 3 of 7 papers
Define bounded minimalization of a predicate P.

Also asked in Summer 2026 Q4a OR, Summer 2023 Q5c

(b)
4 marksAsked in 2 of 7 papers

Discuss primitive recursive functions with the help of a suitable example.

Also asked in Summer 2024 Q5c

(c)
7 marksAsked in 2 of 7 papers

Design a PDA to accept strings with more a’s than b’s. Also trace out the same on input string abbabaa.

Also asked in Summer 2026 Q4c OR

(a)
3 marksSame type asked in 4 of 7 papers
Define ambiguous grammar. Check whether the CFG with productions,
S → a | Sa | bSS | SSb | SbS is ambiguous or not.

Also asked in Summer 2026 Q3b OR, Winter 2024 Q2c OR, Winter 2023 Q3a OR

(b)
4 marks

For each of the following, describe the language generated by given CFG:

i)S → SaS | b
ii)S → aT | bT | Λ T → aS | bS
(c)
7 marksSame type asked in 7 of 7 papers
Define Chomsky Normal Form (CNF). Convert the following CFG into
its equivalent CNF.
S → aY | Ybb | Y
X → Λ | a
Y → aXY | bb | XXa

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

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
Summer 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) (Winter 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