UnFoldPrep
Browse Archive
Gujarat Technological UniversitySummer 2024 Examination

GTU 2160704 Theory of Computation (TOC) Summer 2024 Paper Solution & PDF

B.E. · Computer Engineering · Semester 6 · Subject Code: 2160704
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)

What are existential quantifiers? If the statement (p) says: “There are some people who work at some place for some time.” How can you write it as a quantified statement?

3 Marks
(b)
Explain the strong principle of mathematical induction.
4 Marks
(c)

Write the pumping lemma for regular languages and show how it is used to show that a language is not regular.

7 Marks

Question 2

14 MarksMedium
(a)
Write all the strings with length less than 4 generate by following grammar:

(𝑥 + 𝑦)∗ 𝑎𝑏 (𝑎 + 𝑎𝑏)∗

3 Marks
(b)
What do we understand by the two different statements: 𝑝 → 𝑞 and 𝑃 ⇒ 𝑄?
Are they similar or different?
4 Marks
(c)

Show that for any NFA accepting a language L over 𝛴∗, there is an FA that also accepts L.

7 Marks
OR OPTION
(c)
Show that any regular language can be accepted by a finite automaton.
7 Marks

Question 3

14 MarksMedium
(a)
Explain the difference between ambiguous grammar and unambiguous grammar.
3 Marks
(b)
For the given ambiguous grammar, find its equivalent unambiguous grammar:
S → ABA
A→ aA|ꓥ
B →bB|ꓥ
4 Marks
(c)
Explain all the closure properties of CFG.
7 Marks
OR OPTION
(a)
What is the dangling else problem?
3 Marks
(b)
Describe the language generated by this grammar:
S→ aA | bC | b
A→ aS | bB
B → aC | bA | a
C → aB | bS
4 Marks
(c)

Explain how every regular expression can be converted to its equivalent grammar with an example.

7 Marks

Question 4

14 MarksMedium
(a)
What do we mean by instantaneous description of a PDA?
3 Marks
(b)
Write the pumping lemma for the context free languages.
4 Marks
(c)
Construct a DPDA to accept the strings with equal number of 0’s and 1’s.
7 Marks
OR OPTION
(a)

Explain the difference or similarity between language accepted by PDA with empty stack and language accepted by PDA with a state.

3 Marks
(b)
Define: Top-Down PDA corresponding to a CFG.
4 Marks
(c)
Construct a Nondeterministic PDA for balanced strings of parenthesis.
7 Marks

Question 5

14 MarksMedium
(a)
Define: “Primitive Recursive Functions”
3 Marks
(b)
Explain in short: “Universal Turing Machine.”
4 Marks
(c)
Draw a Turing Machine to accept {𝑠𝑠 |𝑠 ∈ {𝑎, 𝑏}∗}
7 Marks
OR OPTION
(a)
Define: “Bounded Quantifications”
3 Marks
(b)
Explain in short, “Multi-tape Turing Machine”
4 Marks
(c)
Draw a Turing Machine to accept palindromes over {a,b}*
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