UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2025 Examination

GTU 3160704 Theory of Computation (TOC) Winter 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 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)

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.

3 Marks
(b)

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.
4 Marks
(c)

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

7 Marks

Question 2

14 MarksMedium
(a)

Convert the following Mealy machine into its equivalent Moore Machine:

3 Marks
(b)
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}
4 Marks
(c)

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

7 Marks
OR OPTION
(c)

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

7 Marks

Question 3

14 MarksMedium
(a)

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
3 Marks
(b)

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

4 Marks
(c)

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

7 Marks
OR OPTION
(a)
Discuss μ-recursive functions.
3 Marks
(b)
Describe recursively enumerable languages and recursive languages.
4 Marks
(c)

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

7 Marks

Question 4

14 MarksMedium
(a)
Discuss pumping lemma for context-free languages.
3 Marks
(b)
Discuss two situations of Turing machine crashing with example.
4 Marks
(c)

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

7 Marks
OR OPTION
(a)

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

3 Marks
(b)
Define - Pushdown Automaton and acceptance by a PDA
4 Marks
(c)

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

7 Marks

Question 5

14 MarksMedium
(a)
Define bounded minimalization of a predicate P.
3 Marks
(b)

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

4 Marks
(c)

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

7 Marks
OR OPTION
(a)
Define ambiguous grammar. Check whether the CFG with productions,
S → a | Sa | bSS | SSb | SbS is ambiguous or not.
3 Marks
(b)

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

i)S → SaS | b
ii)S → aT | bT | Λ T → aS | bS
4 Marks
(c)
Define Chomsky Normal Form (CNF). Convert the following CFG into
its equivalent CNF.
S → aY | Ybb | Y
X → Λ | a
Y → aXY | bb | XXa
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) (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 PDF