Gujarat Technological UniversitySummer 2024 examination

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

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

Q.1

14 Marks
(a)
3 marks

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?

(b)
4 marks
Explain the strong principle of mathematical induction.
(c)
7 marks

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

Q.2

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

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

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

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

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

Q.3

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

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

Q.4

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

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

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

Q.5

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

More Theory of Computation papers

Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.

Summer 202570 marks · 5 questions

Other Semester 6 subjects

BE Computer

116AG01
Deep Learning and Neural Network
2160701
Software Engineering
2160707
Advanced Java
2160708
Web Technology

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 (2) →Report a typo or correction
ViewDownload PDF