2
1. Which of the following strings 0001, 01001, 0000110 are accepted by the dfa in Figure 2.1?
2. For ( = {a, b} construct dfa’s that accepts the sets consisting of
a. all strings with exactly one a.
As done in class:
b. all strings with at least one a.
c. all strings with no more than three a’s. (notice how the states indicate # of a’s).
d. all strings with at least one a and exactly two b’s.
e. all the strings with exactly two a’s and more than two b’s.
Give dfa’s for the languages
a. L = {ab5wb2 : w ( {a, b}*}
b. L = { abnam : n ≥ 2, m ≥ 3}
c. L = {w1abw2 : w1 ( {a, b}*, w2 ( {a, b}*}
This is any string containing ab somewhere in it.
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 : na(w) mod 3 > 1}
d. L = {w : na(w) mod 3 > nb(w) mod 3}
e. L = {w : (na(w) – nb(w)) mod 3 > 0}
f. L = {w : (na(w) + 2nb(w)) mod 3 < 2}
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. Find dfa’s for the following languages over {a, b}:
a. L = {w: w contains no runs of length less than four}
b. L = {w: every run of a’s has a length of either two or three}
c. L = {w : there are at most two runs of a’s of length three}
State 0: no runs, State 1: one run, State 2: two runs, State 3: more than two runs (reject)
d. L = {w : there are exactly two runs of a’s of length three}
Same as in part c, but only state 2 and the previously accepting states after it would now be accepting.
9. Consider the sets of strings on {0, 1} defined by the requirements below. Construct dfa’s.
a. Every 00 is followed immediately by a 1
b. all strings containing 00 but not 000
c. The leftmost symbol differs from the rightmost
d. Every substring of four symbols has at most two 0’s
e. All strings of length five or more in which the fourth symbol from the right end is different than
the leftmost symbol.
f. All strings in which the leftmost two symbols and the righmost two symbols are identical.
g. All strings of length four or greater in which the leftmost 3 symbols are the same, but different from the rightmost symbol.
10. Construct a dfa that accepts strings on {0, 1} if and only if the value of the string, viewed as the binary representation of a number, is equal to zero modulo 5.
11. Show that the language L = {vwv: v, w ( {a,b}*. |v| = 2} is regular.
12. Show that L = {an: n ( 4} is regular.
13. Show that the language L = {an: n ( 0, n ( 4} is regular.
14. Show that the language L = {an: n is either a multiple of three or a multiple of 5} is regular.
Since 15 is the least common multiple of 3 and 5, we can do modulo 15 arithmetic with the accepting states as shown above.
15. Show that the language L = {an: n is a multiple of three but not a multiple of 5} is regular.
[pic][pic]
-----------------------
1
0
0
0
q2
q1
q0
1
1
a,b
b
b
a[pic][pic]
q2
a
q1
q0
a, b
b
q1
q0
a[pic][pic]
b
b
b
b
a,b
q4+
q3
q2
q1
q0
a
a
a
a
a
a
a
a
q20
q10
q2+0
q00
q2+2
q22
q12
q02
q01
a
a
a
a
a
a
b
b
b
b
b
q2+1
b
b
b
a
a
q11
q21
b
b
b
b
a
a
a
q2+2++
q22+
q12+
q02+
a,b
b
b
b
a
b
b
a
b
b
b
b
b
a
a
b
a
a
a
a
a
a,b
b
b
b
a,b
a
a
a
a
a
a
b
a,b
b
b
b
a
a
b
a,b
a
b
1
0
a,b
2
a,b
a,b
1
0
a,b
a,b
2
a,b
4
3
a,b
a,b
b
b
a
1
0
a
2
a
b
10
a
a
21
11
01
20
00
b
b
b
b
b
b
a
a
a
b
b
b
a
12
a
a
22
02
a
a
aaaa
aaa
aa
a
a
a
a
a
b
b
(
a
trap
b
a
a,b
b
a
a
b
b
b
b
bbbb
bbb
bb
b
b
b
a,b
a
a
a
a
b
b
b
b
2
b
b
a
b
a
a
a
a
b
a
b
a
a
a
a
a
b
a,b
2+
b
b
b
b
b
b
b
0
1
a
a
a
0
0,1
0
0
1
1
1
0,1
1
0
[pic][?]\]bcdfghoprsuwx~ƒ„†‡ÚÛÜÝÞðò0
0
0
1
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
2
3
a.b
1
0
0
1
1
1
0
0
1
1
0
4
a
a
a
a.b
a.b
a
b
a.b
a
b
b
b
a
a
b
b
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
10
14
13
12
11
9
8
7
6
5
4
3
2
1
0
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.