Q.1
14 Marks(a)
Show that (𝑝 → ¬ 𝑝) 𝘝 (¬ 𝑝 → 𝑝) is a tautology.
(b)
Prove that for any; 𝑛 ≥ 4, 𝑛! > 2𝑛.
(c)
Explain the concept of “Language” and discuss how FA, which accepts or rejects a language, is constructed using a regular expression.
Gujarat Technological UniversitySummer 2025 examination
GTU 2160704 Theory of Computation (TOC) Summer 2025 Question Paper & PDF
B.E. · Computer Engineering · Semester 6 · Subject code 2160704
- 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.
Noted. This paper is in our queue now. Check back tomorrow.
We could not record that here. Email the paper name to hirenjsca@gmail.com and we will add it.
Q.2
14 Marks(a)
Define: Context Free Language.
(b)
Write only the algorithmic steps to minimize a given finite automata.
(c)
Apply the rules to convert NFA to FA and create a minimum state FA for the given NFA here.
OR
(c)
Apply pumping lemma for regular languages and prove that the language of palindromes is not regular.
Q.3
14 Marks(a)
Apply the rules and draw NFA – λ for ((0)* + (1)*) (00)*(1)
(b)
Apply the rules to construct NPDA for accepting a palindrome.
(c)
Apply the rules and convert regular expression to regular grammar for the given regular expression. (011 + 1)* (01)*
OR
(a)
Apply the rules to find λ - closure of set of states for the given NFA- λ and find λ(A), λ(B), λ(C) and λ(D). 𝒒 𝜹(𝒒, 𝝀) 𝜹(𝒒, 𝟎) 𝜹(𝒒, 𝟏) A {B} {A} ∅ B {D} {C} ∅ C ∅ ∅ {B} D ∅ {D} ∅
(b)
Explain Context Free Languages.
(c)
Apply the method to check if the given grammar is unambiguous or not:
expr → expr + expr | expr * expr | (expr) | dQ.4
14 Marks(a)
Why is the “Pushdown” automata called “push-down” automata?
(b)
Given a regular expression, you can always create a PDA for it. Explain the statement.
(c)
Apply the rules and draw the TM for the language of odd palindromes.
OR
(a)
The FA is more powerful than DPDA. Explain if True or False?
(b)
Discuss the pumping lemma for CFL.
(c)
Apply the rules and draw the TM to accept the language L = {ab}*{aba} over Σ = {a,b}*
Q.5
14 Marks(a)
Define decidability of a language.
(b)
Discuss Chomsky hierarchy.
(c)
Discuss Primitive Recursive Functions.
OR
(a)
What is a post correspondence problem?
(b)
Discuss Church-Turing thesis.
(c)
Show how all computable functions are 𝜇 -recursive.
More Theory of Computation papers
Questions repeat across sessions. Working through two or three papers shows you which topics GTU asks most.
Other Semester 6 subjects
BE Computer
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 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.