a.1) Generate regular expressions for the following languages where,

i. {w I w contains at least three 1s} ii. {w I w contains the substring 101} iii. {w I w is a string of even length} iv. {w I w has at least one 1} v. {w | the length of w is a multiple of 3}

a.2) Give the formal definition of the following NFA in Figure: 1 and convert it into an equivalent DFA.

(10 + 15 Marks)

= {0, 1}