Thapar University 2006 B.E Computer Science Theory Of Computations - Question Paper

Thapar Institute of Engineering & Technology
B.Tech CS (4th Year)
Final Term exam
CS012 (Theory Of Computations)

Thapar Institute of Engineering & Technology, Patiala Computer Science & Engineering Department B.E. (Computer Engineering) 4^th Year 1st Semester End Semester Test

Course Code: CS-013    Date: 05/12/06

Course Name: Theory of Computations    Time Allowed: 3 Hr.

Instructor: Shalini Batra    Max. Marks: 45

Note : Each question carries equal marks .Attempt any five questions.

Only first five answers will be evaluated

Make suitable assumptions,with reasoning, if required.

Q1 .a) Give the DFA accepting the following language over the alphabets { 0,1} ( no NFA required)    (5)

The set of all strings beginning with 1 that, when interpreted as a integer is multiple of 5. For example string 101,1010,1111 are in the language ;

0,100,111 are not.

Convert the following MealvMachine to Moore Machine :

)a) e

b) Find the regular expression for the following DFA: (X

c)

Check whether the following language is Context free or not(3)

L= {aⁱbⁱc^k/i<j<k}

Convert the following CFG into CNF    (3)

S->aSa; S-B;B-bbC; B -> b b ; C -> e ; C -> c C

Find a Context Free Grammar for the following regular expression over the alphabet {0,1}    (3)

(Oil + 1)' (01)

Draw the TM for the following:-    (5)

All words with odd number of letters that have a as the middle letter

(Eg. aaa, abaab,bab, etc.)

Give the trace for the string abbabba on the machine designed above.

(2)

Give the rules for finding useless symbols.    (2)

Consider the following grammar:-    (4)

S S+ S / S-S / SxS / S/S / (S) /a

(S/S indicate S divide by S)

1.    Give the leftmost derivation for string a + (a x a) / a-a

2.    Give the rightmost derivation for string a + (a x a) / a-a

3.    Give the parse tree for leftmost and rightmost string derived above.

Draw the PDA which accepts the following language:-    (4)

All strings with the same number of a's and b's

Give the language of this CFG : S-aS/bS/a    (1)

Write short notes on the following:-    (3 X 3)

1.    Any three variants of TM

2.    ED of a PDA

3. P and NP problems.

Q6.

Attachment: thapar-university-2006-b-e-computer-science-25964-1.pdf

Earning:   Approval pending.