UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2024 Examination

GTU 3160704 Theory of Computation (TOC) Summer 2024 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)
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.
3 Marks
(b)
Given three statements p, q and r. 𝑝: 𝑎 = 1, 𝑞: 𝑏 = 0, 𝑟: 𝑐 = 3.
𝑊𝑟𝑖𝑡𝑒 𝑡ℎ𝑒 𝑓𝑜𝑙𝑙𝑜𝑤𝑖𝑛𝑔 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡𝑠 𝑠𝑦𝑚𝑏𝑜𝑙𝑖𝑐𝑎𝑙𝑙𝑦, 𝑢𝑠𝑖𝑛𝑔 𝑝, 𝑞, 𝑟, ⋁, ⋀ , ¬ 𝑎𝑛𝑑 →
𝑜𝑛𝑙𝑦.
1Either 𝑎 = 1 or 𝑏 ≠ 0.
2𝑏 = 0 , but neither 𝑎 = 1 𝑛𝑜𝑟 𝑐 = 3.
3
4
5
6
4 Marks
(c)
Discuss pumping lemma for regular languages.
7 Marks

Question 2

14 MarksMedium
(a)
Define Chomsky Normal Form of grammar.
3 Marks
(b)
Define a Moore machine.
4 Marks
(c)
Apply the rules and convert the given NFA-λ to FA.
7 Marks
OR OPTION
(c)

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

7 Marks

Question 3

14 MarksMedium
(a)

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.

3 Marks
(b)

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

4 Marks
(c)

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

7 Marks
OR OPTION
(a)

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

3 Marks
(b)

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

4 Marks
(c)

Apply the rules and show step by step conversion of the following grammar to CNF.

S → ASAaB
A → BS
B → bϵ
7 Marks

Question 4

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

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

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

Question 5

14 MarksMedium
(a)
Explain the concept of undecidable problems.
3 Marks
(b)
Discuss multi-tape Turing machine.
4 Marks
(c)
Write a note on Primitive Recursive functions.
7 Marks
OR OPTION
(a)

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

3 Marks
(b)

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

4 Marks
(c)
Define and explain Bounded Quantification.
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 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 PDF