UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2024 Examination

GTU 3160704 Theory of Computation (TOC) Winter 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 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Define Finite Automata (FA) with an example.
3 Marks
(b)
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.
4 Marks
(c)

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

7 Marks

Question 2

14 MarksMedium
(a)
Define ε-closure(q) with an example.
3 Marks
(b)
State the difference between NFA and DFA.
4 Marks
(c)
Prove by pumping lemma, that the language 0n1n is not regular.
7 Marks
OR OPTION
(c)

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.
7 Marks

Question 3

14 MarksMedium
(a)
State the definition of Pushdown automata.
3 Marks
(b)

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

4 Marks
(c)

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

7 Marks
OR OPTION
(a)
State and prove the pumping lemma for CFL.

What is its main application? Give an example.

3 Marks
(b)
Compare Deterministic PDA and Non deterministic PDA.
4 Marks
(c)

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

7 Marks

Question 4

14 MarksMedium
(a)

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

3 Marks
(b)

What is chomsky normal form? Explain with an example

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

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

4 Marks
(c)
Convert the following grammar into CNF
S→cBA, S→A, A→cB, A→AbbS, B→aaa
7 Marks

Question 5

14 MarksMedium
(a)

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

3 Marks
(b)
Mention the difference between P and NP problems.
4 Marks
(c)

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

7 Marks
OR OPTION
(a)
What is a recursively enumerable language?
3 Marks
(b)
Mention the difference between decidable and undecidable problems.
4 Marks
(c)
Explain NP-complete problems with an example
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) (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 PDF