Gujarat Technological UniversityWinter 2024 examination

GTU 3160704 Theory of Computation (TOC) Winter 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 2:30 PM – 5: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. 7 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
Define Finite Automata (FA) with an example.
(b)
4 marksSame type asked in 4 of 7 papers
Write regular expressions for the following.
i)Binary numbers that are multiple of 2.
ii)Strings of a's and b's with no consecutive a's .
iii)Strings of a's and b's containing consecutive a's.

Also asked in Summer 2026 Q2a, Winter 2025 Q3a, Winter 2023 Q2b

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

Construct a DFA for the language over {0, 1}* such that it contains “000” as a substring.

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

Q.2

14 Marks
(a)
3 marksSame type asked in 2 of 7 papers
Define ε-closure(q) with an example.

Also asked in Summer 2023 Q3a OR

(b)
4 marks
State the difference between NFA and DFA.
(c)
7 marks
Prove by pumping lemma, that the language 0n1n is not regular.
(c)
7 marksSame type asked in 4 of 7 papers

What is ambiguous grammar? Is the following grammar ambiguous?

1E→ E+E |E*E | id
2E→ E+E|E*E|(E)|a Justify your answer.

Also asked in Summer 2026 Q3b OR, Winter 2025 Q5a OR, Winter 2023 Q3a OR

Q.3

14 Marks
(a)
3 marksAsked in 5 of 7 papers
State the definition of Pushdown automata.

Also asked in Winter 2025 Q4b OR, Summer 2025 Q2a, Winter 2023 Q4a OR, Summer 2023 Q4a

(b)
4 marks

Is NPDA (Nondeterministic PDA) and DPDA (Deterministic PDA) equivalent? Illustrate with an example.

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

Construct PDA for the language L={wwR ∣ w∈(a+b)* }

Also asked in Summer 2026 Q4c, Winter 2023 Q5b, Winter 2023 Q5b OR

(a)
3 marks
State and prove the pumping lemma for CFL.

What is its main application? Give an example.

(b)
4 marksAsked in 2 of 7 papers
Compare Deterministic PDA and Non deterministic PDA.

Also asked in Summer 2023 Q4a OR

(c)
7 marks

Is it true that non deterministic PDA is more powerful than that of deterministic PDA? Justify your answer.

Q.4

14 Marks
(a)
3 marksSame type asked in 5 of 7 papers

Construct a CFG for set of strings that contain equal number of a’s and b’s over ∑ = {a,b}.

Also asked in Summer 2026 Q3c, Winter 2025 Q2b, Summer 2025 Q3c, Summer 2025 Q3b OR, Winter 2023 Q3a

(b)
4 marksAsked in 2 of 7 papers

What is chomsky normal form? Explain with an example

Also asked in Summer 2024 Q2a

(c)
7 marks
Convert the following grammar G in greibach normal form. S→ABb|a
A→aaA|B
B→bAb
(a)
3 marks
What is a Turing machine?
(b)
4 marks

Design a Turing machine with no more than three states that accepts the language a(a+b)*. Assume ∑ = {a,b}

(c)
7 marksSame type asked in 7 of 7 papers
Convert the following grammar into CNF
S→cBA, S→A, A→cB, A→AbbS, B→aaa

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

Q.5

14 Marks
(a)
3 marksAsked in 4 of 7 papers

When we say a problem is decidable? Give an example of an undecidable problem.

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

(b)
4 marks
Mention the difference between P and NP problems.
(c)
7 marks

Prove that for two recursive languages L1 and L2 their union and intersection is recursive.

(a)
3 marksAsked in 3 of 7 papers
What is a recursively enumerable language?

Also asked in Winter 2025 Q3b OR, Summer 2023 Q5a OR

(b)
4 marks
Mention the difference between decidable and undecidable problems.
(c)
7 marks
Explain NP-complete problems with an example

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
Summer 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) (Winter 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