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 **Z** → **Z**

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:

*f(bbac,b)*
*f(bbac,c)*
*f(λ,q)*
*f(b,b)*
*f(b,c)*

## 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!]