\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Homework 1}
\duedate{Due: Monday April 10, 2017}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
Upload a {\bf single file} to Gradescope for each group.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
For this {\bf first homework set} you will be graded in two ways: first, each question will be scored according to the standards and rubrics you can expect for the rest of the quarter. However, this score will not be recorded as your grade; you will also
be assigned points according to the extent to which your work demonstrates
``a fair effort attempt" at all parts of the question and this score will be recorded as your HW1 score.\\
Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. \\
{\sc Reading} Sipser Chapter 0 and Section 1.1
\newline
{\sc Key Concepts} Sets, integers, sequences, functions, relations,
predicates, graphs, trees, strings, languages, lexicographic ordering,
boolean logic, proof by construction, proof by contradiction, proof by induction,
finite automata (DFA), computation trace, accept / reject, language of an automaton,
regular language, union of languages, concatenation of languages, star of a language.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 9 points}) In this problem, we'll use the following
definitions (from page 44) of operations on languages (sets of strings)
$A, B$:
\begin{description}
\item[Union] $A \cup B = \{ x ~|~ x \in A ~\text{or}~ x \in B\}$
\item[Concatenation] $A \circ B = \{ xy ~|~ x \in A ~\text{and}~ y \in B\}$
\item[Star] $A^*= \{ x_1 x_2 \ldots x_k ~|~ k \in \mathbb{Z} ~\text{and}~k \geq 0 ~\text{and each}~ x_i \in A\}$
\end{description}
For each of the following sets of strings over the alphabet $\{a,b\}$, answer the following questions
(1) Is $\varepsilon$ (the empty string) in the set?
(2) What's an example of a string over $\{a,b\}$ of length at least $3$ that is in the set
(or why isn't there such an example)?
(3) What's an example of a string over this alphabet of length at least $3$
that is not in the set (or why isn't there such an example?
\begin{itemize}
\item[(a)] $\{ w \in \{a,b\}^*~|~ \exists y ( w = yy) \} $
\item[(b)] $\{ w ~|~ w \in \{a,b\}^* \} \circ \{ w ~|~ w \in \{a,b\}^* \}$
\item[(c)] $\{ w ~|~ w \in \{a,b\}^* \} \cup \{ w ~|~ w \in \{a,b\}^* \}$
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 6 points})
In class (see slides 19 and 33 of lecture 1), we talked about how decision
problems are coded by sets
of strings. For each of the following, (1) describe a way in
which strings can be used to code instances of the problem, (2)
describe the set of strings associated with the problem, (3)
give an example of a string over your chosen alphabet that is
in this language, and (4) give an example of a string over your
chosen alphabet that is not in this language. The first
example has been worked out for you.
\begin{itemize}
\item[Ex.] Problem: Is a given integer prime?
\begin{itemize}
\item {\bf Alphabet} $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. {\bf Coding inputs}
using decimal representation of positive integers.
\item {\bf Set associated with the problem}
\begin{align*}
\{ w ~|~ &w~\text{is a nonempty string over the alphabet and starts} \\
&\text{ with
a digit other than $0$ and represents a prime integer}\\
&\text{ in the usual
decimal representation} \}
\end{align*}
\item {\bf Example of a string in the language of the problem} $2$
because this is a string over the specified alphabet and represents
a prime number (its only positive divisors are $1$ and itself).
\item {\bf Example of a string not in the language of the problem} $10$
because this is a string over the specified alphabet and represents
a number that is not prime (its divisor $2$ is neither $1$ nor $10$).
\end{itemize}
{\it Alternatively} we could have chosen a different alphabet, for example $
\{0,1\}$, with a different encoding (e.g.\ the binary representation of
integers). Notice that, in this case, $10$ would actually be in the language of the problem.
\item[(a)] Context: an automated toll-booth gate opens when coins
totaling at least 25 cents have been paid. The only accepted coin
denominations are nickels (worth 5 cents), dimes (worth 10 cents),
and quarters (worth 25 cents).
Problem: Does a sequence of coins paid to an automated
toll-booth open the gate?
\item[(b)] Problem: Is a given RGB code a shade of purple (i.e.\ just a
combination of red and blue; no contribution from green)?
{\it Note:} For this question, you may use the following supplemental
resource with background on RGB codes \url{https://www.w3schools.com/colors/colors_rgb.asp}
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Consider the DFA, $M$, whose state
diagram is given by:
\begin{center}
\includegraphics[width=3in]{hw1.png}
\end{center}
\begin{itemize}
\item[(a)] What is the language recognized by $M$? Give an
informal description in English and briefly justify your answer.
\item[(b)] If $x \in L(M)$, will the string obtained by flipping bits
in $x$ (changing $0$ to $1$ and $1$ to $0$) also be in $L(M)$?
Why or why not?
\item[(c)] Write the formal definition of $M = (Q, \Sigma, \delta, q_0, F)$. Use a table to define $\delta$.
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 8 points}) For this question,
you will use {\bf JFLAP} and the {\bf haskell} environment.
For support setting these up, please see
the class website \url{http://cseweb.ucsd.edu/classes/sp17/cse105-ab},
search for ``Tools". The files you'll need for this question
are available on the website, near where you downloaded the PDF
of the homework questions.
\begin{itemize}
\item[(a)]
Load the file \texttt{HW1.hs} into the haskell interpreter by running
\cmd{ghci HW1.hs} at the command line shell prompt.
Then, at the ghci prompt, execute \cmd{evalDFA machine1 "011"}
to run the DFA \cmd{machine1} (defined in \texttt{HW1.hs})
on input string ``011''.
Pick some more strings (over the alphabet $\Sigma=\{0,1\}$)
and run the DFA on each of them. If the output is ``True",
the string is accepted; if it's ``False",
the string is rejected.
Find one string over $\Sigma$ that is accepted, and one that
is rejected.
\item[(b)] Look at the definition of \cmd{machine1} in the \texttt{HW1.hs} file (open the file in a text editor of your choice).
Based on the haskell code, and your previous tests,
draw the state diagram of this machine using JFLAP. Save your diagram in a JFLAP file named
\texttt{machine1.jff}. Use JFLAP's ``Input" menu to check that the
diagram you drew agrees with your observations in part (a) for
the two strings you found. You can check if the machine in your state diagram
accepts the correct language by loading \cmd{HW1test.hs} in ghci
(with the command \cmd{:l "HW1test.hs"}) and then running \cmd{test}.
(Alternatively, if you exited ghci, you can run the test directly from the shell
by issuing the command \cmd{runhaskell HW1test.hs}.)
This assumes that the files \texttt{HW1.hs}, \texttt{HW1test.hs} and your
\texttt{machine1.jff} are in your working directory.
If the testing program reports any errors, fix them. When your solution passes all tests,
take a screenshot of your \texttt{machine1.jff} in JFLAP and include it in
your PDF file as the solution to this part of this question.
\item[(c)] \emph{Optional; not for credit:} Describe the language recognized by \cmd{machine1}.
{\it Hint:} Think of the input strings as binary numbers, written left-to-right as usual, e.g., the input string $110$ represents the number $6$. You can describe the language
with a sentence of the form ``The set of all integers $n$, written in binary, such that \ldots''.
{\it Second hint:} Can you relate this example to question 2 from this week's Discussion
worksheet?
\item[(d)] \emph{Optional; not for credit:}
Using haskell, you can even write programs that output finite automata.
Look at the definition of \cmd{buildMachine} in \texttt{HW1.hs}. It is a program
that on input a positive integer $n\geq 1$, outputs a DFA
$\cmd{buildMachine n}$. You can test these automata on any input of your choice
as usual, e.g., by evaluating $\cmd{evalDFA (buildMachine 42) "10001001"}$.
Can you find a {\bf nonempty} string which is not accepted by $\cmd{buildMachine 128}$?
How many states does $\cmd{buildMachine 128}$ have?
Compare the haskell code for $\cmd{buildMachine}$ and $\cmd{machine2}$.
Can you give a formal description of the language of $\cmd{(buildMachine n)}$ for every positive integer $n$?
\end{itemize}
\end{problem}
\begin{problem}[5.] ({\bf 2 points})
\begin{itemize}
\item Enroll in the Piazza site for this class: \url{http://piazza.com/ucsd/spring2017/cse105}.
\item Confirm you have access to this class via Gradescope \url{https://gradescope.com/} using your \texttt{ucsd.edu} email address. If you
do not have access and are enrolled in the class, please post
a private note on Piazza with your name, PID, and which section you're enrolled in.
\item Register your iClicker at \url{https://www1.iclicker.com/register-clicker/}. It is {\bf not enough} to register your remote on TritonEd for this
class.
\item Complete the CSE 105 start of quarter survey:
\url{https://goo.gl/forms/OaIMJXjbI4woGL8s1}
\end{itemize}
To receive credit for this question, submit screen-captures of each group member's account logged into Piazza and write
out the statement ``each group member completed the survey" (we're
using the honor system here; please act with integrity!).
\end{problem}
\end{document}