CS402 4th assignment, July, 2010

[usman malik]

Question No 1: Marks: 5

Find the prefixes of Q in R where Q and R are languages given below:

Q={ ababa , aabbbbbbb,baabba , babbaaaaaa }

R={ aababa , bbaabba , bbaababa, aaaabbbbbbb, abbabbaaaaaa}

Question No. 2

By marking the states, decide whether the following FA accepts any word or not? Marks: 5

Note: Show all steps







Question No. 3 Marks: 5

Describe the language (in English) generated by the following CFG:

S  XY
X  aX | bX | 
Y  baa | bab | bba | bbb

Question No. 4 Marks: 5

Construct the CFG that generates the language L = {w  {a, b}*: length(w)  2 and w begins with b and ends in aa or bb}.



plz give me solution................