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

\newcommand{\IS}{{\rm ISAAC}}
\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 Homework 4 Morally Due Feb 27 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
(40 points-10 points each)
For each of the following languages:
\begin{itemize}
\item
State REGULAR or NOT REGULAR. This should be the FIRST THING on your paper.
(In the past some guy wrote incoherent things so I could not 
tell which direction they are trying to prove. DON'T BE THAT GUY!)
\item 
If REGULAR than give a DFA or NFA or regex or textbook regex for it. 
The DFA or NFA may be given as either a picture or a transition table. 
You MAY use DOT DOT DOT. 
\item 
If NOT REGULAR than PROVE IT.
You MAY use DOT DOT DOT.
\end{itemize} 

\begin{enumerate}
\item 
$L_1=\{ a^na^n \st n\ge 1000\}$.


\item 
$L_2=\{ a^na^n \st n\le 1000\}$.


\item
$L_3=\{ a^{\floor{\log_2 n}}  \st n\ge 1\}.$


\item
For this problem $\Sigma=\{a,b\}$. 
RECALL that $\#_\sigma(w)$ is the number of $\sigma$'s in $w$.
We generalize this to allow $\sigma$ to be a string. 

{\bf Definition} $\#_{ab}(w)$ is the number of times the string $ab$ occurs in $w$. 
                 $\#_{ba}(w)$ is the number of times the string $ba$ occurs in $w$. 
(We can replace $ab$ and $ba$ with any element of $\Sigma^*$.) 

$$L_4= \{ w \st \#_{ab}(w)=\#_{ba}(w) \}.$$

\noindent
{\it Examples} 

$aba\in L_4$ since $\#_{ab}(w)=1$ and $\#_{ba}(w)=1$. 

$abaaaaaab\notin L_4$ since $\#_{ab}(w)=2$ and $\#_{ba}(w)=1$. 

\end{enumerate}

\newpage 

\item 
(30 points--10 each)
For each of the following languages show that they are NOT regular.
\begin{enumerate}
\item 
$L_5=\{ w \st \#_a(w)=2\#_b(w)\}$.



\item 
$L_6=\{ w \st 2\#_a(w)=3\#_b(w)\}$.



\item
Let $c,d\in\N$, $c,d\ge 1$.

$$L_7=\{ w \st c\#_a(w)=d\#_b(w)\}$$ 


\end{enumerate} 

\newpage

\item
(30 points) 

{\bf Definition} Let $w\in\Sigma^*$. Then $\IS(w)$ is the set of words that can be
formed by removing any set of symbols from $w$. For example

$$\IS(abab) = \{e, a, b, aa, ab, ba, bb, aab, aba, abb, bab, abab \}$$

If $L$ is a langauge (a subset of $\Sigma^*$) then 

$$\IS(L) = \bigcup_{w\in L} \IS(w).$$

For example if $L=\{abab,bbbb\}$ then

$$\IS(L) = \{e, a, b, aa, ab, ba, bb, aab, aba, abb, bab, bbb, abab, bbbb \}$$

Show that if $L$ is regular then $\IS(L)$ is regular. 


\end{enumerate} 

\end{document}