Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Fill in true or false:
x ∈ {w,x,y,z}T/F?
w ∈ {(w,x),(y,z),(w,z)}T/F?
y ∈ {{w,x},{y},{z}}T/F?
(x,y) ∈ {(w,x),(y,x),(z,x)}T/F?
 

Problem 2

Explcitly write down all the elements of the set {Q,A}x{0,3,5}:
 

Problem 3

Fill in true or false:
{} ⊆ {w,x,y,z}T/F?
{(y,z),(w,z)} ⊆ {(w,x),(y,z),(w,z)}T/F?
{y} ⊆ {{w,x},{y},{z}}T/F?
{{y}} ⊆ {{w,x},{y},{z}}T/F?
 

Problem 4

Write the cartesian product expression that defines the set:
{(cat,X),(dog,X),(cat,Y),(dog,Y),(cat,A),(dog,A)}
 

Problem 5

Suppose Q1 = {q0,q1,q2} is the set of states for a machine M1, and Q2 = {p0,p1,p2,p3} is the set of states for a machine M2, and suppose that following our algorithm we create a machine M3 accepting the intersection of the languages accepted by M1 and M2. Write down a nice concise mathematical expression (not in english) for the set of states of M3.