CECS 329 Group Assignment 2
Problems
A. Consider the alphabet
Σ =
0
0
0
,
0
0
1
,
0
1
0
,
0
1
1
,
1
0
0
,
1
0
1
,
1
1
0
,
1
1
1
where each symbol is a triple of bits. Provide the state diagram for a DFA that accepts all
words w over Σ for which the top layer of w minus the middle layer of w equals the bottom layer
of w, where each layer is viewed as a binary number whose left most bit is the least significant
bit, and whose rightmost bit is the most significant bit. For example, the DFA should accept
w1 =
01011
00110
01110
1
since the top layer represents the number 26, the middle layer 12, the bottom layer 14, and
26 − 12 = 14. However, it should not accept
w2 =
11001
10100
10011
since the top layer represents the number 19, the middle layer 5, the bottom layer 25, and
19 − 5 6= 25. For each state of your DFA, write a few words that describe the purpose of the
state and/or the situation that the state represents. Show the computation of your DFA on
both inputs w1 and w2. (15 pts)
B. Give a description of the set of binary words that are accepted by the following DFA. Defend
your answer by providing a case-by-case analysis. (10 pts)
a b c d e f
g
0
1
0
1
1
0
0
1
1
0
0
1
0, 1
2
