Gujarat Technological UniversitySummer 2024 examination

GTU 3160704 Theory of Computation (TOC) Summer 2024 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.

5 of 25 questions on this paper were also asked in other years. 5 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
Suppose A and B are sets, 𝑓 = 𝐴 → 𝐵 and 𝑔 = 𝐵 → 𝐴. If 𝑓(𝑔(𝑦)) = 𝑦 for
every 𝑦 ∈ 𝐵, then f is a _______ function and g is a ______ function. Give
reasons for your answers.
(b)
4 marks
Given three statements p, q and r. 𝑝: 𝑎 = 1, 𝑞: 𝑏 = 0, 𝑟: 𝑐 = 3.
𝑊𝑟𝑖𝑡𝑒 𝑡ℎ𝑒 𝑓𝑜𝑙𝑙𝑜𝑤𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡𝑠 𝑠𝑦𝑚𝑏𝑜𝑙𝑖𝑐𝑎𝑙𝑙𝑦, 𝑢𝑠𝑖𝑛𝑔 𝑝, 𝑞, 𝑟, ⋁, ⋀ , ¬ 𝑎𝑛𝑑 →
𝑜𝑛𝑙𝑦.
1Either 𝑎 = 1 or 𝑏 ≠ 0.
2𝑏 = 0 , but neither 𝑎 = 1 𝑛𝑜𝑟 𝑐 = 3.
3
4
5
6
(c)
7 marks
Discuss pumping lemma for regular languages.

Q.2

14 Marks
(a)
3 marksAsked in 2 of 7 papers
Define Chomsky Normal Form of grammar.

Also asked in Winter 2024 Q4b

(b)
4 marks
Define a Moore machine.
(c)
7 marksSame type asked in 3 of 7 papers
Apply the rules and convert the given NFA-λ to FA.

Also asked in Summer 2026 Q2c OR, Winter 2023 Q3c

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

Draw the NFA-λ for r = (0)11* + (101)* 0 and also construct the equivalent NFA and FA for the same.

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

Q.3

14 Marks
(a)
3 marks

Given two languages L1 and L2 defined over Σ = {a, b}∗, L1 accepts palindrome strings and L2 accepts strings with equal number of 0’s and 1’s. Which one of these languages is regular? Give reasons.

(b)
4 marks

Show how, if a pushdown automaton recognizes some language, then it is context free.

(c)
7 marks

If a regular expression is given as (001)* (01 + 10). Apply the rules to construct a regular grammar for this language.

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

Construct a Finite Automata that accepts all strings containing 010 or 111 as sub- string only.

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

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

Apply pumping lemma to show that the language 𝐿 = {𝑎𝑛𝑏𝑛𝑐𝑛 | 𝑛 ≥ 0} is not context free.

Also asked in Summer 2026 Q4b OR, Winter 2025 Q4a OR

(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.

S → ASAaB
A → BS
B → bϵ

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

Q.4

14 Marks
(a)
3 marks
Define DPDA with clear definition of δ (transition function).
(b)
4 marks
Discuss intersection of CFLs with an example.
(c)
7 marksAsked in 2 of 7 papers
Apply the rules and step by step create a Turing Machine to accept 𝐿 = {𝑎𝑛𝑏𝑛}

Also asked in Summer 2023 Q5b

(a)
3 marks

The language of DPDA is called DCFL. Explain whether this statement is true or false.

(b)
4 marks
Discuss complement of CFLs with an example.
(c)
7 marksAsked in 2 of 7 papers
Construct a Turing machine to accept even palindrome over Σ = {a,b}*

Also asked in Summer 2025 Q4c OR

Q.5

14 Marks
(a)
3 marksAsked in 4 of 7 papers
Explain the concept of undecidable problems.

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

(b)
4 marks
Discuss multi-tape Turing machine.
(c)
7 marksAsked in 2 of 7 papers
Write a note on Primitive Recursive functions.

Also asked in Winter 2025 Q5b

(a)
3 marks

A language is decidable if and only if some nondeterministic Turing machine decides it. Explain the statement.

(b)
4 marks

Regular languages and CFLs are both decidable and Turing-recognizable. Explain whether true or false.

(c)
7 marks
Define and explain Bounded Quantification.

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
Summer 202570 marks · 5 questions
Winter 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 2024, 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