Name: ____________________________________________________ Alpha: _____________________

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:
• f(aab)
• f(acab)
• f(λ)

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:
• f(-2,3)
• f(0)
• f(2,-7)

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