CMPS 260 Spring 2025
Homework #1: Sets, Relations, Mealy Machines, DFAs
Due: 2pm, Friday, February 7

1. Let S and T be sets. For each equation provided, indicate the most general (i.e., most inclusive/least restrictive) relationship between S and T that would guarantee that the equation is satisfied.

Hint: Consider the four basic cases: one of S or T is a subset of the other (which has two sub-cases) or neither is a subset of the other (which has two sub-cases, depending upon whether their intersection is empty).

(a) S  =  S ∪ T
(b) S  =  S ∩ T
(c) S ∪ T  =  S ∩ T
(d) (S ∪ T) − T  =  S

2. Recall these definitions pertaining to a binary relation R on a set A:

• R is reflexive iff (x,x) ∈ R for all x ∈ A
• R is symmetric iff (x,y) ∈ R implies (y,x) ∈ R for all x,y ∈ A
• R is transitive iff (x,y) ∈ R and (y,z) ∈ R implies (x,z) ∈ R, for all x,y,z ∈ A

For each binary relation described below on the left, indicate (e.g., using a checkmark) in the table to the right which among the listed properties it possesses. Each relation is to be understood as being on the set A = { a, b, c }.

R1: { (b,c), (c,b) } R2: { (a,b), (b,c), (a,c), (c,c) } R3:  ∅   (i.e., empty set) R4: { (a,b), (c,a) } R5: { (a,a), (b,b), (c,c), (b,a), (b,c) }

Relation Property R1 R2 R3 R4 R5 reflexive           symmetric           transitive

In the previous problem, five relations over A were given and, for each one, you were to have identified which subset of the properties in P it possessed. Hence, at least three of the eight subsets of P were not represented in that problem. Choose two of those three subsets of P, and, for each one, identify it and describe a binary relation over A possessing exactly the properties in that subset.

4. Let R be a binary relation on the set A (i.e., R ⊆ A×A). Give a convincing argument in support of the following statement:  If R is both transitive and symmetric, and for each a ∈ A there is at least one b for which (a,b) ∈ R, then R is also reflexive (and therefore an equivalence relation!).

5. Present a Mealy machine (having {0,1} as both input and output alphabet) that reports the parity of the sum of every length-3 substring of input. That is, for each bit of input, the machine should output either '0' or '1', respectively, in accord with whether the sum of that bit and the two preceding bits is even or odd.

To state it more precisely, suppose that the input string were b₀b₁...b_n-1. Then the output produced by the machine should be c₀c₁...c_n-1, where, for each i, c_i = (b_i-2 + b_i-1 + b_i) % 2. (For convenience, take b_-2 and b_-1 to be 0.)

Hint: The machine must "remember" the two bits most recently read.

6. Present a DFA that accepts the language.

The states should be given meaningful names (e.g., identifying prefixes of the two "target" strings).

7. Present a DFA that accepts the language

The states should be given meaningful names (e.g., identifying prefixes of the two "target" strings).