Download GTU BE/B.Tech 2019 Summer 6th Sem Old 160704 Theory Of Computation Question Paper

Download GTU (Gujarat Technological University) BE/BTech (Bachelor of Engineering / Bachelor of Technology) 2019 Summer 6th Sem Old 160704 Theory Of Computation Previous Question Paper

Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER?VI(OLD) ? EXAMINATION ? SUMMER 2019
Subject Code:160704 Date:18/05/2019
Subject Name: Theory Of Computation
Time:10:30 AM TO 01:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

Q.1 (a) Write Principle of Mathematical Induction. Using Principle of Mathematical
Induction, prove that for every n?1,
n
? i
2
= n(n+1)(2n+1)
i=1 6
07
(b) Define reflexivity, symmetry, and transitivity properties of relations. Consider the
relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2, 3}. Is it
reflexive? Symmetric? Transitive? Justify each of your answers.
07
Q.2 (a) Convert NFA-^ to NFA and DFA. Initial State: A, Final State : D
Q ? (q, ^) ? (q, 0) ? (q, 1)
A {B} {A} ?
B {D} {C} ?
C ? ? {B}
D ? {D} ?

07
(b) Suppose that L1 and L2 are the subsets

Draw the FAs recognizing the following Languages:
? L1 ? L2
? L1 ? L2
07





FirstRanker.com - FirstRanker's Choice


Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER?VI(OLD) ? EXAMINATION ? SUMMER 2019
Subject Code:160704 Date:18/05/2019
Subject Name: Theory Of Computation
Time:10:30 AM TO 01:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.

Q.1 (a) Write Principle of Mathematical Induction. Using Principle of Mathematical
Induction, prove that for every n?1,
n
? i
2
= n(n+1)(2n+1)
i=1 6
07
(b) Define reflexivity, symmetry, and transitivity properties of relations. Consider the
relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2, 3}. Is it
reflexive? Symmetric? Transitive? Justify each of your answers.
07
Q.2 (a) Convert NFA-^ to NFA and DFA. Initial State: A, Final State : D
Q ? (q, ^) ? (q, 0) ? (q, 1)
A {B} {A} ?
B {D} {C} ?
C ? ? {B}
D ? {D} ?

07
(b) Suppose that L1 and L2 are the subsets

Draw the FAs recognizing the following Languages:
? L1 ? L2
? L1 ? L2
07









OR
(b) Define Pumping Lemma for Regular Languages. Use Pumping Lemma to show
that the following languages are not regular.

L = { 0
n
1
2n
| n > 0 }
L = { ww
R
| w ? {0,1}* }
07

Q.3 (a) Define Ambiguous grammar. Write Unambiguous grammar for following
grammar :
E ? E + E | E * E | ( E ) | id
Derive string ?id+id*id? using unambiguous grammar.

07
(b) Given the CFG G, find a CFG G? in Chomsky Normal form generating L(G) ? {
?}
S ? A | B | C
A ? aAa | B
B ? bB | bb
C ? aCaa | D
D ? baD | abD | aa
07
OR
(a) Design Context Free Grammar for following Language :
L = { 0
i
1
j
0
k
| j > i + k }
07
(b) Write Regular Expressions corresponding to each of the following subsets of
{0,1}*
(i) The language of all strings in {0,1}* that containing at least two 0?s.
(ii) The language of all strings containing both 101 and 010 as substrings.
(iii) The language of all strings that do not end with 01.
07



Q.4 (a) Design PDA for the language L = { x ? {a, b}* | na(x) > nb(x) }. 07
(b) Explain Cook?s Theorem. 07
OR
(a) Design PDA for the language L = { xcx
r
| x ? {a, b}* } 07
(b) Write Short note on Any Two :
(i) The Primitive Recursion Function
(ii) P and NP Completeness
(iii) Equivalence Relation
07

Q.5 (a) Design Turing Machine(TM) to accept Palindrome over {a,b}, even as well as
odd.
07
(b) Write Short note on Following:
(i) Halting Problem
(ii) Church Turing Thesis
07
OR
(a) Design Turing Machine to copy string. 07
(b) Explain Time Complexity and Space Complexity. 07




*************
FirstRanker.com - FirstRanker's Choice