\ \ \ Give a regular expression defining each of the following languages over the alphabet

\\\\Sigma ={a,b}

.\ (a)

L={aab,ba,bb,baab}

;\ (b) The language of all strings containing exactly two

b

's.\ (c) The language of all strings containing at least one

a

and at least one

b

.\ (d) The language of all strings that do not end with

ba

.\ (e) The language of all strings that do not containing the substring

bb

.\ (f) The language of all strings in which every

b

is followed immediately by

aa

.\ For the following regular expressions over the alphabet

\\\\Sigma ={a,b}

, give a word description of the\ language and as well, the first five (5) words in the language ordered by cardinality (length of\ the word):\ (a)

(a+b)**abb

\ (b)

ab(a+b)**ba+aba

\ (c)

b^(**)(ab^(**)ab^(**))^(**)

\ (d)

(aa)**(bb)^(**)b

\ (e)

(b+ab)^(**)+(b+ab)**a

\

1) Give a recursive definition for the language STRANGE which is defined over the alphabet ={a,b} and contains words that have an even number of b 's and an odd number of a 's. 2) Consider the following recursive definition of 4-PERMUTATION: Rule 1: 4321 is a 4-PERMUTATION. Rule 2: If wxyz is a 4-PERMUTATION, then so are zxyw and yxzw. Rule 3: no other words belong to 4-PERMUTATION. Give all the words in the language 4-PERMUTATION. 3) Give a regular expression defining each of the following languages over the alphabet ={a,b}. (a) L={aab,ba,bb,baab}; (b) The language of all strings containing exactly two b 's. (c) The language of all strings containing at least one a and at least one b. (d) The language of all strings that do not end with ba. (e) The language of all strings that do not containing the substring bb. (f) The language of all strings in which every b is followed immediately by aa. 4) For the following regular expressions over the alphabet ={a,b}, give a word description of the language and as well, the first five (5) words in the language ordered by cardinality (length of the word): (a) (a+b)abb (b) ab(a+b)ba+aba (c) b(abab) (d) (aa)(bb)b (e) (b+ab)+(b+ab)a 5) For the alphabet ={a,b}, construct an FA that accepts the following languages. (a) L={ all words with exactly one b}. (b) L={ all words with at least one a}. (c) L= \{all words with no more than three b s }. (d) L= \{all words with at least one a and exactly two b 's\} (e) L= \{all words with b as the third letter\} (f) L= \{all words with the number of letters being divisible by 4} (g) L= \{all words that do not have two a 's together or two b 's together }