CS402

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