A. the Language of All Strings Containing Exactly Two a S

NOTE:- All GIRLS STUDENTS WILL FORM ONE GROUP, ALL BOYES STUDENTS WILL BE IN OTHER GROUP. BOTH GROUPS WILL SUBMITE THERE COPY OF SOLUTION FOR ASSINGMENT. DEAD LINE IS MONDAY 05/08/2013 POSITIVELY

Q1:- In each part below, give regular expression and draw an DFA accepting the indicated language over {a, b}.

a. The language of all strings containing exactly two a’s.

b. The language of all strings containing at least two a’s.

c. The language of all strings that do not end with ab.

d. The language of all strings that begin or end with aa or bb.

e. The language of all strings not containing the substring aa.

f. The language of all strings in which the number of a’s is even.

g. The language of all strings in which both the number of a’s and thenumber of b’s are even.

h. The language of all strings containing no more than one occurrence ofthe string aa. (The string aaa contains two occurrences of aa.)

i. The language of all strings in which every a (if there are any) isfollowed immediately by bb.

j. The language of all strings containing both bb and aba as substrings.

k. The language of all strings containing both aba and bab as substrings

Q2:- For each of the following languages, draw anDFA accepting it.

a. {a, b}∗{a}

b. {bb, ba}∗

c. {a, b}∗{b, aa}{a, b}∗

d. {bbb, baa}∗{a}

e. {a} ∪ {b}{a}∗∪ {a}{b}∗{a}

f. {a, b}∗{ab, bba}

g. {b, bba}∗{a}

h. {aba, aa}∗{ba}∗

Q3:- For each of the FAs pictured in given Figures, give a simple verbal description of the language it accepts.

Q4:- Find Minimum states DFA for each case.

Q5:- Each of the following languages is thecomplement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts E = {a, b}.

a. {w | w does not contain the substring ab}

b. {w | w does not contain the substring baba}

c. {w |w contains neither the substrings ab nor ba}

d. {w| w is any string not in a*b* }

e. {w| w is any string not in (ab+)+}

f. {w| w is any string not in a* + b*}

g. {w | w is any string that doesn't contain exactly two a's}

h. {wI|w is any string except a and b}

Q6:- Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts Z = {a, b}.

a. {w |whas at least three a's and at least two b's}

b. {w | w has at exactly two a's and at least two b's}

c. {w|w has an even number of a's and one or two b's}

d. {w | w has an even number of a's and each a is followed by at least one b}

e. {w |w has an even number of a's and one or two b's}

f. {w| whas an odd number of a's and ends with a b}

g. {w | w has even length and an odd number of a's}