\documentclass[12pt]{article}

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

\begin{document}


\centerline{\bf Homework 2 Morally Due Feb 13 at 3:30PM}

\begin{enumerate}
\item
(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?

\newpage
\item
(25 points)
The alphabet is $\{a\}$.
Let $p,q$ be distinct primes that are $\ge 100$. 
Let 

$$L=\{a^i  \st i\not\equiv 0 \pmod{pq}\}.$$
\begin{enumerate}
\item
(10 points)
Describe a DFA for $L$ by giving the state set, the alphabet, the start state, the final states, and the transition function.
Try to minimize the
number of states. 
\item
(15 points)
Describe a NFA for $L$ by giving the state set, the alphabet, the start state, the final states, and the transition function.
It should have much fewer states then the DFA. 
\item
(0 points) For your own interest. Let $p_1,\ldots,p_k$ be the first $k$ primes. 

$$L=\{a^i  \st i\not\equiv 0 \pmod{p_1\cdots p_k}\}.$$
Do the first two parts of this problem for this $L$. 

\end{enumerate}

\newpage

\item
(25 points) Let $p_1,\ldots,p_{k}$ be the first $k$ odd primes.

Let 

Let $L$ be the set of all $a^n$ such that the number of primes $p\in \{p_1,\ldots,p_k\}$
such that $n\equiv 0 \pmod p$ is a square. 

\noindent
{\bf Example:} Say $k=10$. So we are looking at the primes

$$3,5,7,11,13,17,19,23,29,31.$$

If $n$ is divisible by 3 and 13 and 23 and 29 but nothing else in that list
then there are 4 such primes. Since 4 is square, $n\in A$. 

If $n$ is divisible  by 3 and 13 and 23 and 29 and 31 but nothing else in that list
then there are 5 such primes. Since 5 is not a square, $n\notin A$. 

\noindent
{\bf Back to the problem} Describe a DFA for $L$.  You may use DOT DOT DOT. 


\newpage 

\item
(25 points) Let $w^R$ be the reverse of $w$ and let $L^R = \{w : w^R \in L\}$. Prove that if $L$ is regular then $L^R$ is regular. Fill in the following: If the DFA for $L$ has $n$ states, then the DFA for $L^R$ has $XXX(n)$ states. What is $XXX$?

ADDED LATER: Here is how your proof should begin. Let $L$ be a regular language. Let
$L$ be accepted by DFA $(Q,\Sigma,\delta,s,F)$. Give the construction for an NFA for $L^R$.
(Recall that we did this kind of proof for closure under $\cup$. In that case given
two DFAs we constructed the DFA for the intersection of the two languages.)

\newpage

\item
(25 points)
A language $L$ is {\it Sam-Regular} if there exists an NFA $M$, without $e$-transitions,  such that

$x\in L$ iff when you run $M(x)$ the number of possible final states it ends in is PRIME.

Show that If $L$ is {\it Sam-Regular} than $L$ is regular.



\end{enumerate}
\end{document}