How To Exam?

a knowledge trading engine...

Rajasthan Technical University 2009-6th Sem B.Tech Computer Science and Engineering Theory Of Computation - Question Paper

Friday, 24 May 2013 09:55Web

Page 1 of 5

Rajasthan tech. Univercity
B.Tech 3rd Year
2009
Theory Of calculation

Rll No.__L_

Total No. of Questions : 5| (Total No. of Pi{n :4

|2079J

J B.Tcch. Vlth Semester (Main/Back) Examination-2009

Computer Engineering Theory of Computation 6E3018

.Time : 3 Hours Vliiimim Marks: S0

Mia. FaMMf Marks : 24

Instructions to Candidates:

Attempt overall Five Questions selecting one question from each unit All questions cany equal marks. (Schematic diagrams must be shown wherever ~ necessary. Any data you feel trussing may suitably be asshmed and stated clearly. Units of quantities used/calculated must be stated dearly.)

Unit - 1

'1- a) A public telephone (PCO) accepts one or rupees tvyo coins. The call can be made only when the total amount inserted is rupees two. Suppose the telephone has two. LED-GREEN and RED. The GREEN LED is set when the call is being made. The RED LED is set when the total amount inserted is rupees three or more. This call is possible only when. RED is off. Construct a DFA corresponding to this machine. (8)

b) Construct a DFA that accepts the language of all legal infire arithmetic expressions over the alphabet

L = {i;.J>. + .-.*.!} assuming normal precedence rules. <<*)

c) Prove that FA is a computing model however it is not an ideal computing model. (2)

OR

6F.301S/ 5000 <>> (Contd_

a) Construct an NFA that accepts the set of string defined over set |0. 1J that start with 1 and are congruent to 0 module 3

L=jx E¹: x starts with 1 and

|jr|0mod3}

b) Construct a Melay machine which can output EVEN, ODD *ccording as the totaJ number of Is encountered is even or odd. The input symbols are 0 and 1. <4)

c) Consider a Melay machine represented by figure. Construct a Moore machine equivalent to this melay machine (4)

H8 (2) [Contd....

1

a) If <#=({*}.{o}.i) find the language generated by a. (2)

b) Let L be the set of all palindromes over {a, b}. Construct a generating L.

^W(4)

c) Construct an FA equivalent to the regular expression (0+1) * (00+11) (0+1)*

(5)

d) Is ={o^:" W>lj regular? (-5)

OR

a) Prove the following identity (a*ab+ba)*a* = (a+ab+ba)* 76)

b) Show that L = \a^r />isa prime j is not regular! . (6)

c> Design the regular expression for the following language over (a, b)

i) Containing all string with exactly 2 b's

ii) Containing all string begining with a and ending with b.

iii) All string with three consecutive b's. (J)

I

Unit - 3

a) Eliminate useless symbols, useless production, unit productions and m production from the given grammar S-aS|/4|c, A~*a, B~*aa, C -acb (*>

b) Find a grammar in CNF equivalent to the grammar 5->-5j[5 35jj (S being the only variable) (8)

OR

a) Consider the following productions

S-iaB bA. .4 - . H a. B ~*bS a HB h |->r [he string aaabbabbba. Find

i) Left most'derivation

ii) Right most derivation

iii) Pansetree. (J

b) Find a grammar in GN'F equivalent to the grammar

E-*E + T IT.T-*T F/F. F*{E)/a - (8)

Unit - 4

a) Construct a PDA A accepting the set of all strings over |a, b) with equal

4.

e

ie

:t

rrt

is

S)

tic

(6)

:mg

(2)

ltd

number of as and bs. (10)

b) What is difference between finite automation and push down automation.

(6).

OR

Construct a PDA accepting bma" /m,n> l} by null store. Construct the corresponding context free grammar accepting the same set. (16)

Unit - 5

a) Design .a Turipg Machine that checks whether a string of left and right parenthesis is well formed or not. Assume that the input string consisting of a sequence of left and right parenthesis is bounded by . (8i

b) Consider the Turing machine description given in table

Tape Symbols