UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2023 Examination

GTU 3160704 Theory of Computation (TOC) Winter 2023 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)
Say whether the statement (p ᴧ (p → q)) → q is tautology or
contradiction.
3 Marks
(b)

The given relation R on set A= {1,2,3} determine whether the Relation is reflexive, symmetric or transitive, give reason. R ={(1,1), (1,2), (2,1), (2, 2), (3,2),(3,3)}

4 Marks
(c)
Write Principle of Mathematical Induction. And prove for every n ≥ 1,
7 Marks

Question 2

14 MarksMedium
(a)
Define FA and Write recursive definition of NFA
3 Marks
(b)

Find a regular expression of following subsets of {0, 1}*

1The language of all strings that begin or end with 00 or 11.
2The language of all strings ending with 1 and not containing 00.
4 Marks
(c)
Draw Finite Automata to accept following over input alphabets Σ ={0, 1}
i)The language accepting strings not ending with ’01’ .
ii)The language accepting strings not containing substring ‘00’
7 Marks
OR OPTION
(c)

Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. M1-- M2-- Draw FAs recognizing the following languages.

aL1 U L2
bL1 - L2
7 Marks

Question 3

14 MarksMedium
(a)
Find context-free grammar for the language: L= {aibjck | i=j+k}
3 Marks
(b)

Define mealy machine. Design and mealy machine that gives output ‘x’ if input of sequence is abb, otherwise z.

4 Marks
(c)
Convert NFA- Λ to FA for following
GTU Theory of Computation (3160704) Winter 2023 Question 3(c) Diagram
7 Marks
OR OPTION
(a)
Define Ambiguous grammar. for following grammar say whether the
grammar is ambiguous or not. give reason
S→ABA, A→aA | Λ , B→bB | Λ
3 Marks
(b)
Convert the given Moore machine into Mealy machine. Draw state
transition diagram of Mealy machine.
Present
State
Next State Output
0 1
→p0 r q0 ɛ
p1 r q0 1
q0 p1 s0 0
q1 p1 s0 1
r q1 p1 0
s0 s1 r 0
s1 s1 r
4 Marks
(c)
Find minimum state FA for following
GTU Theory of Computation (3160704) Winter 2023 Question 3 OR (c) Diagram
7 Marks

Question 4

14 MarksMedium
(a)
State pumping lemma for context free language.
3 Marks
(b)
Construct PDA for
S → 0AB
A → 1A | 1
B → 0B | 1A | 0
Trace the string 01011 using PDA.
4 Marks
(c)
Write Kleen’s Theorem part -1.
7 Marks
OR OPTION
(a)
Define Push Down Automata
3 Marks
(b)
Using kleene's Theorem Draw NFA-Λ for a given RE aa(ba)*+b*aba*
4 Marks
(c)
Given the context-free grammar G, find a CFG G’ in Chomsky Normal
Form.
S -> AaA | CA | BaB
A -> aaBa | DC
B -> bb | aS
C -> Ca | bC | D
D -> bD | Λ
7 Marks

Question 5

14 MarksMedium
(a)
Explain Universal Turing Machine
3 Marks
(b)
Design a PDA to accept L = {xcy | x, y∈ (a,b)* and |x| = |y|}.
4 Marks
(c)
Develop a Turing Machine to accept palindromes over {a,b}*
7 Marks
OR OPTION
(a)
Define grammar and Chomsky hierarchy.
3 Marks
(b)
Design a PDA to accept L = {aibjCk| j = i+k}.
4 Marks
(c)

Develop a Turing Machine to accept the language L = {X / Na(X)=Nb(X) , X ∈ {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) (Winter 2023, 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