\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{comment} 

\renewcommand{\P}{{\rm P}}
\newcommand{\GEN}{{\rm GEN}}
\newcommand{\DTIME}{{\rm DTIME}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\DM}{{\rm DM}}
\newcommand{\VC}{{\rm VC}}
\newcommand{\IS}{{\rm ISAAC}}
\newcommand{\thCOL}{{\rm 3COL}}
\newcommand{\fourCOL}{{\rm 4COL}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\goes}{\rightarrow}
\newcommand{\nth}{n^{th}}
\newcommand{\N}{\sf{N}}
\newcommand{\Q}{\sf{Q}}
\newcommand{\R}{\sf{R}}
\newcommand{\C}{\sf{C}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}


\begin{document}

\centerline{\bf Optional Project Morally Due May 7  3:30PM}

This is an OPTIONAL PROJECT. It would be more accurate to say its an OPTIONAL HW.
I will not look at it until after the final is graded and the final grades
have been determined.
\begin{enumerate}
\item
If you have a D in the course and do a VERY GOOD JOB on the optional project then I will
bump your grade to a C-.
\item
If you have an F in the course (note- in my 40 years of teaching this has only happened twice)
and you do a VERY GOOD JOB on the optional project then I will bump your grade to a D. 
\item
The following has actually happened. DON"T BE THIS GUY. A guy does badly on the midterm,
does not do the project, gets a D in the course, and THEN asks me if he could do some kind
of optional project to bring his grade up to a C. The answer was of course NO. DO NOT BE THAT GUY.
\item
Students often ask me for sample problems. Consider this to be a set of sample problems whether
you do it or not.
\item
Should you do this if you are in no danger of failing the course? Yes- its a good study aid.
\item
Can this bump your grade from a C to a B or a B to an A or some such? NO. I will only look at those
from the D and F students. 
\item
Start the project NOW. You don't want to do it at the last minute.
\end{enumerate} 



\newpage

\begin{enumerate}

\item
(15 points) 

Let $L_1$ be regular with DFA $(Q_1,\Sigma,\delta_1,s_1,F_1)$. 

Let $L_2$ be regular with DFA $(Q_2,\Sigma,\delta_2,s_2,F_2)$. 

Let $\$$ be a symbol that is not in $\Sigma$. 

Construct a DFA for the language 

$$\{ x\$y \st x\notin L_1 \wedge y\notin L_2 \}.$$

\newpage 

\item 
(15 points) 
Let $G$ be the grammar with rules

$S\goes AB$

$A\goes BA$

$B\goes SA$

$A\goes a$

$B\goes b$. 

Let $L=L(G)$. 

In this problem you will, by hand, do the algorithm for $L\in P$ on the string $abb$. 

Do by hand the algorithm for $L\in P$ on the input $abba$.
In particular, fill in the BLANKS below, explain your work, 
and determine if $abba\in L$.

$\GEN[1,1] = $ BLANK.

$\GEN[2,2] = $ BLANK.

$\GEN[3,3] = $ BLANK.

$\GEN[4,4] = $ BLANK.

\bigskip

$\GEN[1,2] = $ BLANK.

$\GEN[2,3] = $ BLANK.

$\GEN[3,4] = $ BLANK.

\bigskip

$\GEN[1,3] = $ BLANK.

$\GEN[2,4] = $ BLANK.

\bigskip

$\GEN[1,4] = $ BLANK.

Since $\GEN[1,4]$ BLANK, we know that the question $abab\in L$? has the answer BLANK.

\newpage


\item 
(15 points) 
Show that if $L$ is in P then $L^*$ is in P. 


\newpage 

\item
(20 points- 1 point each) 
Assume $\P\ne\NP$. 
The following is a list of problems that are in NP. 
For each one state which of the following holds:

\begin{itemize}
\item
The problem is known to be in $\P$
\item 
The problem is known to NOT be in $\P$. 
\item 
It is NOT KNOWN if the problem is in $\P$.
\end{itemize} 


NOW, here is the list: 

\begin{enumerate}

\item
$\{ (G,k) \st \hbox{$G$ is $k$-colorable } \}.$

\item
$\{ G \st \hbox{$G$ is $1000$-colorable } \}.$

\item
$\{ (G,k) \st \hbox{$G$ has a Vertex Cover of size $k$ } \}.$

(Recall that a {\it Vertex Cover of $G=(V,E)$} is a set $U\subseteq V$
such that every EDGE has at least one vertex in $U$ as an endpoint. 

\item
$\{ G \st \hbox{$G$ has a Vertex Cover of size $\le 1000$ } \}.$

\item
$\{ (G,k) \st \hbox{$G$ has a Dom Set of size $k$ } \}.$

(Recall that a {\it Dom Set of $G=(V,E)$} is a set $U\subseteq V$
such that every VERTEX has at least one vertex in $U$ as a NEIGHBOR.)

\item
$\{ G \st \hbox{$G$ has a Dom Set of size $\le 1000$ } \}.$

\item
$\{ n \st (\exists n_1,n_2,n_3,n_4\in\N)[ n = n_1^2 + n_2^2 + n_3^2 + n_4^2]\}$

(Note that $n$ is in binary. Note that $\N$ includes 0. These hold for the next
two problem as well.) 

\item
$\{ n\in \N \st \hbox{n is prime} \}$

\item
$\{ (n,m) \st \hbox{$n$ has a factor that is $\le m$} \}$

\item
$\{ (G,H) \st \hbox{$G$ and $H$ are isomorphic} \}$

\end{enumerate} 

\newpage

\item
(20 points) This problem uses WS1S notation. Draw the DFA for

$$\{(x,X) \st x+2\in X \}.$$

(NOTE: I posted this optional project on April 4. I had not covered the
material needed to do this problem yet.) 


\newpage

\item
(15 points) Present 5 sets that are not decidable. 
(PRESENT THEM CLEARLY!) 

(NOTE: I posted this optional project on April 4. I had not covered the
material needed to do this problem yet.) 


\end{enumerate}

\end{document}