CS402 Final Exam (Fall 2009) paper

CS402 Final Exam (Fall 2009)

http://www.allvupastpapers.blogspot.com/

Time 2 Hours

Total questions 41

Objective questions 31

Subjective question 10

Question: 31                                       (Marks 1)

Can you say that string of 0’s whose length is a perfect square is not regular?

Question: 32                                       (Marks 1)

Question: 33                                       (Marks 2)

Is the following an FA or TM?

http://www.allvupastpapers.blogspot.com/

Question: 34                                       (Marks 2)

If L is the language that accept even length strings then what strings will Lc accept?

Question: 35                                       (Marks 3)

Define Myhill Nerode theorem

Question: 36                                       (Marks 3)

If L1,L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be

(L1 INTERSECTION L2) Union (L2 INTERSECTION L3) ≠ Ø

http://www.allvupastpapers.blogspot.com/

Question: 37                                       (Marks 3)

How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG?

Question: 38                                       (Marks 5)

What is the difference between concatenation and intersection of two FAs and union and addition of two FAs?

Question: 39                                       (Marks 5)

Use pumping lemma II to show that following language is not regular.

L = {an2 ; n =1,2,3,4…}

http://www.allvupastpapers.blogspot.com/

Question: 40                                       (Marks 10)

Draw Moore Machine equivalent to the following Mealy Machine.

Question: 41                                       (Marks 10)

Write CFG of the following PDA. Also write the stack alphabet and tape alphabet.

http://www.allvupastpapers.blogspot.com/