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

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ? VI (Old) EXAMINATION ? WINTER 2019
Subject Code: 160704 Date: 11/12/2019

Subject Name: Theory Of Computation

Time: 02:30 PM TO 05: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) Explain one to one and onto functions with example. Give inverse of the function
f: R
+
? R
+
, f(X) = X
2

07
(b) Prove 1+2+3+?+n =(n*(n+1)) / 2 using Principal of Mathematical Induction 07

Q.2 (a) Define Regular Expression.
Find Regular Expression corresponding to each of the following subsets of
{0,1}*
1) The Language of all strings containing exactly two 0?s
2) The Language of all strings that end with 01
3) The Language of all strings that begin or end with 00 or 11
07
(b) Draw FAs recognizing following languages,
L1 = { x | 00 is not a substring of x }
L2 = { x| x ends with 01 }
Draw FA accepting the language L1 U L2

07
OR


(b) Explain Distinguishable strings with example. Draw FA corresponding to a
Regular Expression (R.E.) = (11+110)*0, where ? = {0,1}

07
Q.3 (a) Define NFA - ?. Give Recursive Definition of ?* for DFA,NFA and NFA ? ?. 07
(b) Draw NFA recognizing the language ({0,1}*{10} U {00}*{11}*) * using
kleene?s theorem part 1, where ? = {0,1}

07
OR


Q.3 (a) Define Pumping Lemma for Regular Languages. Show that following language
is not a Regular Language using Pumping Lemma
L = {0
i
1
i
| i >=0 }, where ? = {0,1}
07
(b) Define CFG. Give CFG for L = {0
i
1
j
0
k
| j > i+ k }

07
Q.4 (a) Convert following CFG to Chomsky Normal Form,
(1) S AACD
(2) A aAb | ?
(3) C aC | a
(4) D aDa | bDb | ?
07
(b) Define PDA. Give DPDA for CFG S SS | [S] | {S} | ?

07

OR




FirstRanker.com - FirstRanker's Choice
1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ? VI (Old) EXAMINATION ? WINTER 2019
Subject Code: 160704 Date: 11/12/2019

Subject Name: Theory Of Computation

Time: 02:30 PM TO 05: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) Explain one to one and onto functions with example. Give inverse of the function
f: R
+
? R
+
, f(X) = X
2

07
(b) Prove 1+2+3+?+n =(n*(n+1)) / 2 using Principal of Mathematical Induction 07

Q.2 (a) Define Regular Expression.
Find Regular Expression corresponding to each of the following subsets of
{0,1}*
1) The Language of all strings containing exactly two 0?s
2) The Language of all strings that end with 01
3) The Language of all strings that begin or end with 00 or 11
07
(b) Draw FAs recognizing following languages,
L1 = { x | 00 is not a substring of x }
L2 = { x| x ends with 01 }
Draw FA accepting the language L1 U L2

07
OR


(b) Explain Distinguishable strings with example. Draw FA corresponding to a
Regular Expression (R.E.) = (11+110)*0, where ? = {0,1}

07
Q.3 (a) Define NFA - ?. Give Recursive Definition of ?* for DFA,NFA and NFA ? ?. 07
(b) Draw NFA recognizing the language ({0,1}*{10} U {00}*{11}*) * using
kleene?s theorem part 1, where ? = {0,1}

07
OR


Q.3 (a) Define Pumping Lemma for Regular Languages. Show that following language
is not a Regular Language using Pumping Lemma
L = {0
i
1
i
| i >=0 }, where ? = {0,1}
07
(b) Define CFG. Give CFG for L = {0
i
1
j
0
k
| j > i+ k }

07
Q.4 (a) Convert following CFG to Chomsky Normal Form,
(1) S AACD
(2) A aAb | ?
(3) C aC | a
(4) D aDa | bDb | ?
07
(b) Define PDA. Give DPDA for CFG S SS | [S] | {S} | ?

07

OR




2

Q.4 (a) Give Bottom Up PDA for following CFG,
(1) S S+T | T
(2) T T * a | a
07
(b) Prove that following Grammar is an Ambiguous Grammar
S S +S | S*S | (S) | a
Draw parse tree for string a+a*a using above grammar

07
Q.5 (a) Draw Turing Machine (TM) accepting Palindrome over {a,b} 07
(b) Explain following terms
1) P and NP Completeness
2) Time and Space Complexity

07
OR


Q.5 (a) Draw Turing Machine (TM) accepting {SS | S ? {a,b}*} 07
(b) Explain unbounded minimization and ? recursive functions 07

FirstRanker.com - FirstRanker's Choice