Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

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 2

  1. Write down the elements of $\left\{ (k,w) \in \{0,1,2\}\times \{\text{aa},\text{bb},\text{a},\lambda\}\ {\big |}\ k = |w| \right\}$
  2. Draw a DFA that accepts the language: $\left\{ awa \in \{a,b,c\}^* \ {\big |}\ w \text{ contains at least one } c \right\}$

Problem 3

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

Problem 4

Write a C++ or Java implementation of
({q0,q1,q2,q3,q4},{a,b}, 
  | a  b 
--+------
q0| q1 q3
q1| q1 q2
q2| q2 q2
q3| q4 q2
q4| q2 q4
 ,q0,{q1,q4})
It should read in a string from stdin and write "accept" or "reject" to stdout and write absolutely nothing else (unless there's an error). Call your program HWSol.cpp. 
$ ./hwsol 
abba
reject 
$ ./hwsol 
babb
accept

Turn in a printout of the source code of your program, and submit your program using the submit system: 
submit -c=SI342 -p=hw06 HWSol.cpp
If you program in a language other than C++, turn in a screen capture of your program running with the following examples (make sure you get the right answers!)
aaccept
breject
aaaccept
abreject
baaccept
bbreject
ababreject
babbaccept

Note: If you're really ambitious, try writing a program that is able to read in a description of a finite automaton from a file (you can make up any file format you like) and simulate that automaton, rather than hardcoding a single machine into the class. It would be really cool if you could read in a JFLAP .jff file. I'll give you extra credit for this.