(b)L= {ab n a m : n ≥ 2,m ≥3},
(c)L= {w 1 abw 2 : w 1 ∈ {a,b} * ,w 2 ∈ {a,b} * },
(d)L= {ba n : n ≥ 1,n≠ 5}.
6. With Σ = {a,b}, give a dfa for L= w 1 aw 2 : |w 1 |≥ 3, |w 2 |≤ 5}.
7. Find dfa's for the following languages on Σ = {a,b}.
(a) L= {w: |w| mod 3 = 0}.
(b) L= {w: |w| mod 5 ≠ 0}.
(c) L= {w: n a (w) mod 3 > 1}.
(d) L= {w: n a (w) mod 3 >n b (w)mod 3}.
(e) L= {w :(n a (w) – n b (w)) mod 3 > 0}.
(f) L= {w :(n a (w)+2n b (w)) mod 3 < 2}.
(g) L= {w: |w| mod 3 = 0, |w| ≠6}.
* 8. A run in a string is a substring of length at least two, as long as possible and
consisting entirely of the same symbol. For instance, the string abbbaab
contains a run of b's of length three and a run of a's of length two. Find dfa's
for the following languages on {a,b}.
(a) L= {w: w contains no runs of length less than four}.
(b) L= {w: every run of a’s has length either two or three}.
(c) L= {w: there are at most two runs of a’s of length three}.
(d) L= {w: there are exactly two runs of a’s of length 3}.
9. Consider the set of strings on {0,1} defined by the requirements below. For
each, construct an accepting dfa.
(a) Every 00 is followed immediately by a 1. For example, the strings 101,
0010, 0010011001 are in the language, but 0001 and 00100 are not.
(b) All strings containing 00 but not 000.
(c) The leftmost symbol differs from the rightmost one.
(d) Every substring of four symbols has at most two 0’s. For example,
001110 and 011001 are in the language, but 10010 is not since one of its