Problem 4 Assignment 3

Use the Cartesian Product technique from Section 7.5 of the Course Notes to construct a DFSA that accepts binary strings of odd length, and that are multiples of 5 when interpreted as base two numbers. For example, your machine should accept 101 (5 in base two), but not 1111 (15 in base two). State, without proof, the appropriate state invariants (see Section 7.3).


My teammate and I worked on a solutiona nd came up with the following:

The following is the state invariants of a DFSA that accepts binary strings of
odd length, and that are multiples of 5 when interpreted as base two numbers.

Note: In the expression x%5 = n, n denotes the remainder of x divided by 5.


State invariants of a DFSA that accepts binary strings of odd length.

Q_1 = {q'_0, q'_1}.

Sigma_1 = {0, 1}.

s_1 = {q'_0)}

F_1 = {q'_1}
q'_0 if the length of x is even
P_1(x): delta*(s_1, x) = q'_1 if the length of x is odd


State invariants of a DFSA that accepts binary strings that are multiples
of 5 when interpreted as base two numbers:

Q_2 = {q_(epsilon), q_0, q_1, q_2, q_3, q_4}.

Sigma_2 = {0, 1}.

s_2 = {q_(epsilon)}

F_2 = {q_0}

--------------q_(epsilon) if x is an exmpty string
--------------q_0 if x%5 = 0 when interpreted as a base two number
--------------q_1 if x%5 = 1 when interpreted as a base two number
P_2(x): delta*(s_2, x) = q_2 if x%5 = 2 when interpreted as a base two number
--------------q_3 if x%5 = 3 when interpreted as a base two number
--------------q_4 if x%5 = 4 when interpreted as a base two number


State invariants of a DFSA that accepts binary strings of odd length, and
that are multiples of 5 when interpreted as base two numbers.

Q = {q_(epsilon), q_0, q_1, q_2, q_3, q_4, q'_0, q'_1}.

Sigma = {0, 1}.

s = {(q_(epsilon), q'_0)}

F = {(q_0, q'_1)}

------------(q_(epsilon), q'_0) if x is an empty string
------------(q_0, q'_0) if length of x is even and x%5 = 0
------------(q_0, q'_1) if length of x is odd and x%5 = 0
------------(q_1, q'_0) if length of x is even and x%5 = 1
------------(q_1, q'_1) if length of x is odd and x%5 = 1
P(x): delta*(s, x) = (q_2, q'_0) if length of x is even and x%5 = 2
------------(q_2, q'_1) if length of x is odd and x%5 = 2
------------(q_3, q'_0) if length of x is even and x%5 = 3
------------(q_3, q'_1) if length of x is odd and x%5 = 3
------------(q_4, q'_0) if length of x is even and x%5 = 4
------------(q_4, q'_1) if length of x is odd and x%5 = 4