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

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

1
Seat No.: ________ Enrolment No.___________

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ? VI (New) EXAMINATION ? WINTER 2019
Subject Code: 2160704 Date: 09/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.



MARKS

Q.1 (a) Define ? bijection function. Check whether the function ?? ? ?? ? ?? defined
by ?? (?? ) = 2?? is a bijection function or not. Justify your answer.

03
(b) Draw an FA that recognizes the language of all strings containing even no
of 0?s and even no of 1?s over ? = {0,1}. Also write a regular expression for
the same language.

04
(c) Write the principle of Mathematical Induction. Prove using mathematical
induction that for every n ? 0,

?
1
i (i + 1)
n
i=1
=
n
n + 1


(Consider the sum on the left is 0 for n = 0)

07
Q.2 (a) Find regular expression and also derive the words corresponding to the
language defined recursively below over ? = {a, b} .
i. a ? L
ii. For any x ? L, xa and xb are elements of L

03
(b) Define ? Equivalence relation. A relation on the set {1,2,3} is given as R =
{(a, b) | a ? b is an even no}. Check whether R is equivalence relation or
not. Give reasons.

04
(c) Give transition table for PDA recognizing the following language and trace
the move of the machine for input string abcba:
L = {xcx
r
| x ? {a, b}
?
}

07
OR


(c) Give transition table for PDA accepting the language of all odd-length
strings over {a, b} with middle symbol a. Also draw a PDA for the same.

07
Q.3 (a) Let FA 1 and FA 2 be the FAs as shown in the figure recognizing the languages
L1 and L2 respectively. Draw an FA recognizing the language, L1 U L2.
FA 1 :


FA 2 :

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

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ? VI (New) EXAMINATION ? WINTER 2019
Subject Code: 2160704 Date: 09/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.



MARKS

Q.1 (a) Define ? bijection function. Check whether the function ?? ? ?? ? ?? defined
by ?? (?? ) = 2?? is a bijection function or not. Justify your answer.

03
(b) Draw an FA that recognizes the language of all strings containing even no
of 0?s and even no of 1?s over ? = {0,1}. Also write a regular expression for
the same language.

04
(c) Write the principle of Mathematical Induction. Prove using mathematical
induction that for every n ? 0,

?
1
i (i + 1)
n
i=1
=
n
n + 1


(Consider the sum on the left is 0 for n = 0)

07
Q.2 (a) Find regular expression and also derive the words corresponding to the
language defined recursively below over ? = {a, b} .
i. a ? L
ii. For any x ? L, xa and xb are elements of L

03
(b) Define ? Equivalence relation. A relation on the set {1,2,3} is given as R =
{(a, b) | a ? b is an even no}. Check whether R is equivalence relation or
not. Give reasons.

04
(c) Give transition table for PDA recognizing the following language and trace
the move of the machine for input string abcba:
L = {xcx
r
| x ? {a, b}
?
}

07
OR


(c) Give transition table for PDA accepting the language of all odd-length
strings over {a, b} with middle symbol a. Also draw a PDA for the same.

07
Q.3 (a) Let FA 1 and FA 2 be the FAs as shown in the figure recognizing the languages
L1 and L2 respectively. Draw an FA recognizing the language, L1 U L2.
FA 1 :


FA 2 :

03
2


(b) Define ? Moore machine. Convert the following Moore machine into its
equivalent Mealy machine:

Old state
After input a After input b
Output
New state New state
?q
0
q
1
q
2
0
q
1
q
3
q
2
1
q
2
q
2
q
3
0
q
3
q
3
q
3
1


04
(c) Convert the following NFA - ? into its equivalent DFA that accepts the
same language:


07
OR


Q.3 (a) Prove that ? ?If there is a CFG for the language L that has no ?-productions,
then there is a CFG for L with no ?-productions and no unit productions?.
Support your answer with the help of the following CFG:
S ? A | bb
A ? B | b
B ? S | a

03
(b) Write CFG for the following languages :
i. {a
i
b
j
c
k
| i = j + k}

ii. {a
i
b
j
c
k
| j = i or j = k}

04
(c) Define ? ambiguous grammar, leftmost derivation. Check whether the
following grammars are ambiguous or not. Justify your answer with proper
reason.

i. S ? ABA
A ? aA | ?
B ? bB | ?
ii. S ? A | B
A ? aAb | aabb
B ? abB | ?

07

Q.4

(a)

Describe the language generated by the following grammars:

i. S ? aA | bC | ??
A ? ???? | bB
B ? ???? | bA | ??
C ? aB | bS
ii. S ? aT | bT | ?
T ? aS | bS



03


(b)

Discuss ? Nondeterministic Turing Machines and Universal Turing
Machines


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

GUJARAT TECHNOLOGICAL UNIVERSITY

BE - SEMESTER ? VI (New) EXAMINATION ? WINTER 2019
Subject Code: 2160704 Date: 09/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.



MARKS

Q.1 (a) Define ? bijection function. Check whether the function ?? ? ?? ? ?? defined
by ?? (?? ) = 2?? is a bijection function or not. Justify your answer.

03
(b) Draw an FA that recognizes the language of all strings containing even no
of 0?s and even no of 1?s over ? = {0,1}. Also write a regular expression for
the same language.

04
(c) Write the principle of Mathematical Induction. Prove using mathematical
induction that for every n ? 0,

?
1
i (i + 1)
n
i=1
=
n
n + 1


(Consider the sum on the left is 0 for n = 0)

07
Q.2 (a) Find regular expression and also derive the words corresponding to the
language defined recursively below over ? = {a, b} .
i. a ? L
ii. For any x ? L, xa and xb are elements of L

03
(b) Define ? Equivalence relation. A relation on the set {1,2,3} is given as R =
{(a, b) | a ? b is an even no}. Check whether R is equivalence relation or
not. Give reasons.

04
(c) Give transition table for PDA recognizing the following language and trace
the move of the machine for input string abcba:
L = {xcx
r
| x ? {a, b}
?
}

07
OR


(c) Give transition table for PDA accepting the language of all odd-length
strings over {a, b} with middle symbol a. Also draw a PDA for the same.

07
Q.3 (a) Let FA 1 and FA 2 be the FAs as shown in the figure recognizing the languages
L1 and L2 respectively. Draw an FA recognizing the language, L1 U L2.
FA 1 :


FA 2 :

03
2


(b) Define ? Moore machine. Convert the following Moore machine into its
equivalent Mealy machine:

Old state
After input a After input b
Output
New state New state
?q
0
q
1
q
2
0
q
1
q
3
q
2
1
q
2
q
2
q
3
0
q
3
q
3
q
3
1


04
(c) Convert the following NFA - ? into its equivalent DFA that accepts the
same language:


07
OR


Q.3 (a) Prove that ? ?If there is a CFG for the language L that has no ?-productions,
then there is a CFG for L with no ?-productions and no unit productions?.
Support your answer with the help of the following CFG:
S ? A | bb
A ? B | b
B ? S | a

03
(b) Write CFG for the following languages :
i. {a
i
b
j
c
k
| i = j + k}

ii. {a
i
b
j
c
k
| j = i or j = k}

04
(c) Define ? ambiguous grammar, leftmost derivation. Check whether the
following grammars are ambiguous or not. Justify your answer with proper
reason.

i. S ? ABA
A ? aA | ?
B ? bB | ?
ii. S ? A | B
A ? aAb | aabb
B ? abB | ?

07

Q.4

(a)

Describe the language generated by the following grammars:

i. S ? aA | bC | ??
A ? ???? | bB
B ? ???? | bA | ??
C ? aB | bS
ii. S ? aT | bT | ?
T ? aS | bS



03


(b)

Discuss ? Nondeterministic Turing Machines and Universal Turing
Machines


04
3
(c) Find a minimum-state FA for the following FA that recognizes the same
language using the minimization algorithm:


07
OR


Q.4 (a) Find the CFG for the regular expression : (011 + 1)
?
(01)
?


03
(b) Prove that the language L = {a
n
b
n
ab
n+1
| n = 1, 2, 3, ? } is nonregular
using pumping lemma.

04
(c) Convert the following CFG into its equivalent CNF:

S ? TU | V
T ? aTb | ?
U ? cU | ?
V ? aVc | W
W ? bW | ?

07
Q.5 (a) Convert the following CFG into its equivalent PDA.

S ? AB
A ? BB
B ? AB
A ? a
B ? a | b

03
(b) Show using the pumping lemma that the following language is not a CFL.

L = {a
i
b
j
c
k
| i < j < k}

04
(c) Draw a Turing Machine that accepts the language {a
n
b
n
a
n
| n ? 0} over
{a, b}
?
. Also trace the TM on input string aaabbbaaa.

07
OR


Q.5 (a) Define Context Sensitive Language and Context Sensitive Grammar. Write
CSG for L = {a
n
b
n
c
n
| n ? 1}.

03
(b) Define - Primitive recursive functions and also give complete primitive
recursive derivations for the function, f ? N ? N defined by Add(x, y) =
x + y.

04
(c) Draw a Turing Machine that accepts the language {xx | x ? {a, b}
?
}. Also
trace the TM on input string aa.


07
*************

FirstRanker.com - FirstRanker's Choice