Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Consider the following function (recall that Σ* denotes the set of all strings over alphabet Σ, λ denotes the empty string, and N denotes the non-negative integers):
f:{a,b}* → N
f(w) = 2|w|
Give the values of each of the following expressions, or "error" if the function's argument is outside of its domain:
 

Problem 2

Consider the following function (recall that Z denotes the integers and N denotes the non-negative integers):
f:N x ZZ
f(a,b) = a - b
Give the values of each of the following expressions, or "error" if the function's argument is outside of its domain:
 

Problem 3

Let Σ = {a,b,c} and recall that Σ* denotes the set of all strings over alphabet Σ. Consider the following function:
\[ \begin{array}{l} f:\Sigma^* \times \Sigma \rightarrow \{\text{true},\text{false}\}\\ f(w,x) = \left\{ \begin{array}{cl} \text{false} & \text{if $w = \lambda$}\\ \text{true} & \text{if $x$ is the first character of $w$}\\ \text{false} & \text{if $x$ isn't the first character of $w$} \end{array} \right. \end{array} \]
Give the values of each of the following expressions, or "error" if the function's argument is outside of its domain:

Problem 4

Give a formal definition for the "Union Algorithm", i.e. the algorithm that takes two machines as input and produces a machine that accepts the union of the languages accepted by the two input machines. [Note: If you're not basing your answer on the intersection algorithm described in the notes for this class, you'll deserve the grade you get!]