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*.