RTU 2016 Question Paper Semester VI Computer Science and Engineering Theory of Computation

hy -i /p1{

TotalNoofPages: tr
ft1
N 6F,6023
o
\o
B. Tech. VI-Sem. (Main/Back) Exam., ApriUM ay-e016
Computer Science
EI
\o 6CS3A Theory of Computation
Common for IT
Time: 3 Hours Maximum Marks: E0
Min. Passing Marks (Main & Back): 26
Instructi.ons to Candidate s : -

Attempt any five questions, selecting one question
from each unit. All
Questions carry equal marks. schematic diagrams must be shown
wherever necessary. Any data you feel missing may suitably be assumed
and stated clearly.
units of quantities used/ calculated must be stated clearly.
ttse of following supporting material is permitted during examination.
(Mentioned inform No. 205)
1. NIL
2. NIL

UNIT.I
Q.l (a) M = ({q1, q2, q3}, {0, t}, 6, ql, tq3)) is nondeterministic finite automaton,
where 5 is given by
t8l
6 (q1, 0) = {q2, q3}, 6 (q1, l) = {ql }

5 (q2, 0) = {ql, q2}, 6 (q2, l) =
Q

6 (q3, 0) = {q2} 5 (q3, l) = {ql, q2}
Construct an equivalent DFA.

(b) Explain the model of a discrete automaton, also describe its characteristics.
tgl

[6E6023] Page 1 of4
[68801

OR

Q.l (a) Describe the block diagram of a finite automaton. Consider the transition system
given below.
U0
:\
Y
onff @
n/o
1011/0

q'2

U0

Determine the initial states, the final state and the acceptability of 101011 and
111010. t8l
(b) Prove that for any ffansition function 5 and for any fwo input string x and y.
5 (q, xY) = 5 (5 (q, x), Y) t8l

UNIT.II
Q.2 (a) If G = ({S}, {0, 1}, {s + 0 SI, S -> n}, S), findL (G) with explanation. t8l
(b) Find the language generated by the grammar S + AB, A -+ A 110, B -+ 2813.
Can the above language be generated by a grammar of higher type? tSl

OR
Q.2 (a) Prove that:
(1 +00* 1)+(1 +00* 1)(0+ 10* 1) * (0+ 10x 1)=0* 1 (0+ 10x 1)* t8l
(b) Consider a finite automaton, with n - moves, given in a figure
Obtain an equivalent automaton without n - moves. t8l

l6E6o23) Page2 of 4 [6880]

T]NIT.III
model and its role, also illustrate the move
*"t"jr;j
Q.3 Define pushdown automaton
details.
OR
t8l
Q.3 (a) Consider the following
productions:

S-+aBlbA
A+aSlbAAla
B-+bSlaBBlb
for the string a a abb ab b b a' find

(i) the leftmost derivation'
(ii) the rightmost derivation' and
(iii) the Parse tree
t8l
(b) Reduce the following grammars in Chomsky normal form:
(i) S + leloe, A -+ lealos l0' B -+ onn lrs lr
(ii) G = ({S}, {a, b, c}' {S + a lb lcSS}' S)
(iii) S -+abSblalaAb' A ->bSlaAAb

and its working functions'
t8l
Q.4 (a) Explain Turing machine model input
)|; ;;;.;;" i* description below. Draw the computation sequence of the
t8l

q1
lLqz 0 Rq1

q2 b Rq3 OLqZ lLqz
b Rq4 b Rq5
q3
0 Rq5 0 Rq4 1 Rq4
q4
o'Lqz
@
Page 3 of4 [68801
[6E6023]

OR

Q.4 Design a Truing machine over { 1, b} which can compute a concatenation function
overl= {1}.

If a pair of words (w1, w2) is the input, the output has to be w1 w2. t16I

Q.5 Explain the model of Linear bounded automaton, also explain the relationship between
LBA and context sensitive languages. tt6]

OR
Q.5 Write short note on (any 2):- [8x2=16]
(a) Chomsky Hierarchy of languages
(b) Properties of LBA
(c) Context sensitive languages

[6E6023'] Page 4 of4 [6880]

OR
Q.1 (a) Describe the block diagram of a finite automaton. Consider the transition system
given below.
Lt0

q0 on rtil___4 @

xl'
U0

Determine the initial states, the final state and the acceptability of 101011 and
I 1 1010. t8l
(b) Prove that for any transition function 6 and for any two input string x and y.
6 (q, xY) = 6 (6 (q, x), y) t8l
UNIT.II
Q.2 (a) If G=({S}, {0, 1}, {S-+0SI,S-+n},S),findL(G)withexplanation. I8l
(b) Find the language generated by the grammar S -+ AB, A -+ A 110, B + 2813.
Can the above language be generated by a grammar of higher type? t8l
OR
Q.2 (a) Prove that:
(l +00* 1)+(1 +00 * 1)(0+ 10* 1) * (0+ 10* 1)=0* I (0+ 10x 1)* t8l
(b) Consider a finite automaton, with A - moves, given in a figure
Obtain an equivalent automaton without A - moves. t8l

16E60231 Page2 of4 [68801

UNIT.III
its role, also illustrate the move
relation in
model and
Q.3 Define pushdown automaton t16l
details'
OR
t8l
productions:
Q.3 (a) Consider the following
S-raBlbA
A+aSlbAAla
B-+bSlaBBlb
for the string a a ab b ab b b a' find
(i) the leftmost derivation'
(iD the rightmost derivation' and
(iil) the Parse tree
form: t8l
(b) Reduce the following graflrmars in Chomsky normal
(D s -+ I alon, A -+ I ee los I 0' B -+ onn lrs lr
(ii) G = (tS), {a, b' c}' tS -+ a tb I cSS}' S)
(iii) S -rabSblalaAb' A ->bStaAAb

(a) Explain Turing machine model and its working functions'
t8l
Q.4 sequence
tLo innrrf
of the input
description below. Draw the computation
6 ;;;;;r* t8l

+ql lLqz 0 Rq1

q2 b Rq3 0Lq2 lLqz
b Rq4 b Rq5
q3
0 Rq5 0 Rq4 1 Rq4
q4
0'Lqz

Page 3 of4
[6880]
[6E6023]

OR

Q.4 Design a Truing machine over {1, b} which can compute a concatenation function
overl= {l}.

If a pair of words (w1, w2) is the input, the output has to be wl w2. t16l

UNIT.V

Q.5 Explain the model of Linear bounded automaton, also explain the relationship between
LBA and coRtext sensitive languages. tl6l

OR
Q.5 Write short note on (any 2):- [8x2=16]
(a) Chomsky Hierarchy of languages
(b) Properties of LBA
(c) Context sensitive languages

16860231 Page 4 of4 [68801