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

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

1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VI(NEW) ? EXAMINATION ? SUMMER 2019
Subject Code:2160704 Date:16/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.

MARKS

Q.1 (a) Define 1) Parse tree 2) Ambiguous grammar 03
(b) Prove by mathematical induction: for every n>=1, 1 + 3 + 5 + ?
+ (2n - 1) = n
2

04
(c) Consider the grammar: S ?ABA, A ?aA | ?, B ?bB | ?
Is given grammar ambiguous? If so then remove ambiguity
07

Q.2 (a) Design Moore machine to generate 1?s complement of binary
number.
03
(b) Write Regular Expression over the alphabets {a, b} consisting
strings:
? Second last character as ? a?
? Starting with ?a? and ending with ?b?
04
(c) Find context free grammar for the following language.
L1={a
i
b
j
c
k
| i = j + k}, L2= (011+1)* (01)*, L3=(0+1)1*(1+(01)*)
07
OR
(c) Draw FA for following languages:
? L1 = {w | 00 is not substring of w}
? L2 = {w | w ends in 01}
Find FA accepting languages (i). L1 ? L2 and (ii). L1 ? L2
07
Q.3 (a) Give the left linear grammar for RE (10)
*
1 03
(b) Minimize the given DFA:
State / Transition a b
? 1 {3} {2}
2 {4} {1}
3 {5} {4}
4 {4} {4}
5 {3} {2}

04
(c) Eliminate useless symbols, ?-productions and unit productions
for the following grammar:
S ?0A0 | 1B1 | BB, A ?C, B ?S | A, C ?S | ?
07
OR
Q.3 (a) Consider the grammar:
S ? aAS | a
A ? SbA | SS | ba
Derive left most and right most derivation of string aabbaa using
given grammar.
03
(b) Give CFG for following languages:
1). L = a*b* 2). L = {a
n+2
b
n
| n >= 0}
04
(c) Construct finite automata for following left linear grammar:
S ? X0 | Y1
07
FirstRanker.com - FirstRanker's Choice
1
Seat No.: ________ Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER ?VI(NEW) ? EXAMINATION ? SUMMER 2019
Subject Code:2160704 Date:16/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.

MARKS

Q.1 (a) Define 1) Parse tree 2) Ambiguous grammar 03
(b) Prove by mathematical induction: for every n>=1, 1 + 3 + 5 + ?
+ (2n - 1) = n
2

04
(c) Consider the grammar: S ?ABA, A ?aA | ?, B ?bB | ?
Is given grammar ambiguous? If so then remove ambiguity
07

Q.2 (a) Design Moore machine to generate 1?s complement of binary
number.
03
(b) Write Regular Expression over the alphabets {a, b} consisting
strings:
? Second last character as ? a?
? Starting with ?a? and ending with ?b?
04
(c) Find context free grammar for the following language.
L1={a
i
b
j
c
k
| i = j + k}, L2= (011+1)* (01)*, L3=(0+1)1*(1+(01)*)
07
OR
(c) Draw FA for following languages:
? L1 = {w | 00 is not substring of w}
? L2 = {w | w ends in 01}
Find FA accepting languages (i). L1 ? L2 and (ii). L1 ? L2
07
Q.3 (a) Give the left linear grammar for RE (10)
*
1 03
(b) Minimize the given DFA:
State / Transition a b
? 1 {3} {2}
2 {4} {1}
3 {5} {4}
4 {4} {4}
5 {3} {2}

04
(c) Eliminate useless symbols, ?-productions and unit productions
for the following grammar:
S ?0A0 | 1B1 | BB, A ?C, B ?S | A, C ?S | ?
07
OR
Q.3 (a) Consider the grammar:
S ? aAS | a
A ? SbA | SS | ba
Derive left most and right most derivation of string aabbaa using
given grammar.
03
(b) Give CFG for following languages:
1). L = a*b* 2). L = {a
n+2
b
n
| n >= 0}
04
(c) Construct finite automata for following left linear grammar:
S ? X0 | Y1
07
2
X ? Y1
Y ? Y0 | 1
Q.4 (a) Compare PDA with FSM 03
(b) Write a note on DPDA and NPDA 04
(c) Design a pushdown automata to check well-formed parenthesis. 07
OR
Q.4 (a) Give the formal definition of Turing machine. Also compare the
power of DFA, NFA, DPDA, NDPA and TM
03
(b) Write a note on post machines. 04
(c) Design a Turing machine to reverse the string over alphabet {0,
1}
07
Q.5 (a) Compare and contrast push down automata and Turing machine. 03
(b) Enlist limitations of Turing machines. 04
(c) Design a Turing machine which accepts the language consisting
string which contain aba as a substring over alphabets {a, b}
07
OR

Q.5 (a) Discuss universal Turing machine 03
(b) Write a short note on Halting problem 04
(c) What is decidability? How to prove that the given language is
undecidable? List some undecidable problems.
07

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