VUsolutions Transferred to AchiKhasi.com

From December 2011, this blog www.VUsolutions.blogspot.com is transferred to http://achikhasi.com/vu/ . So, you may visit http://achikhasi.com/vu/ for latest study related help.

Back to home VUsolutions

VUsolutions Fans Club [join us for MORE solutions]

VUsolutions on Facebook

CS402

Tuesday, April 27, 2010 Posted In Edit This
Question No.1 Marks: 4

a) Give regular expressions of the following languages over Σ={0,1}:
1. All strings having no pair of consecutive zeros.
2. All strings having exactly two 1’s or three 1’s not more than it.

b) Show that the Regular expression ^ + 0(0+1)*+(0+1)*00(0+1)* is equivalent to ((0*1)*01*)*

Solution:
a)
1. {0,1,01,11,10,101,010,011,110…………}
2. {011,110,0110.10101.1101,01101,111,0111,…………….}
b)
Both are equivalent because they generate the same language


Question No. 2 Marks: 4

a) Give recursive definition for the language ODD, of strings defined over ∑={-,0,1,2,3,4,5,6,7,8,9},

b) Give recursive definition for the language of palindromes having odd length

Solution:
a)
step1: 1 is in odd
Step2: If x is in odd then x+2 and x-2 are also in odd.
step3: No strings except those constructed in above are allowed to be in odd

b)
Step 1: 1 is in palindrome
Step2: if x is palindrome, than s(x) Rev(S) and xx is also be palindrome whereas belongs to E*
Step3: no string except one, constructed in above, are allowed to be in Palindrome

Back to home VUsolutions

Shaadi.com: Just create ur account & find ur partner or EARN money, its reall & EASY

VUsolutions Followers (Join NOW and Get Extra Benefits)

Install LATEST toolbar having lot of features - GET solutions on Desktop

toolbar powered by Conduit
Caliplus 300x250 NoFlam VitoLiv 468x60 GlucoLo