\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx}

\begin{document}

\homework{3}{Prof. Nancy Lynch}{Due: Monday, February 26, 2007,
  5PM}{Elena Grigorescu}



\noindent{\bf Reading:  Sipser, Sections 1.3 and 1.4}

\bigskip
\begin{problem}
Taken from Sipser 1.18.  
Give regular expressions generating the following languages.  In all
cases the alphabet is $\{0,1\}$.
\begin{enumerate}
\item $L_1 = \{w|w \mbox{ contains at least three } 1s \}$.
\item $L_2 = \{w|w \mbox{ has length at least } 3 \mbox{ and its third
  symbol is } 0 \}$.
\item $L_3 = \{w|w \mbox{ doesn't contain the substring } 110 \}$.
\item $L_4=\{w| \mbox{ every odd position of } w \mbox{ is a } 1 \}$.
\item $L_5=\{w|w \mbox{ contains at least two } 0s \mbox{ and at most
  one } 1 \}$.
\end{enumerate}
\end{problem}

\begin{problem}
Sipser 1.19. 
Use the procedure described in Lemma 1.55 to convert the following
regular expressions to nondeterministic finite automata.
\begin{enumerate}
\item $(0 \cup 1)^*000(0 \cup 1)^*$
\item $(((00)^*(11))\cup 01)^*$
\item $\emptyset^*$
\end{enumerate}
\end{problem}

\begin{problem}
Sipser 1.21. Use the procedure described in Lemma 1.60 to convert the
following finite automata to regular expressions.
\begin{center}
\includegraphics[height=2in]{figs/2dot1.eps}
\end{center}
\end{problem}


\begin{problem}
Use the pumping lemma to show that the following languages are not regular.
\begin{enumerate}
\item 
$A_1 = \{ w w w | w \in \{0,1\}^* \}$.
\item 
$A_2 = \{ w \in \{0,1\}^* | \mbox{ the number of } 0s \mbox { in } w
  \mbox{ is a perfect square } \}$. 

\end{enumerate}
\end{problem}

\begin{problem}
Based on Sipser 1.30. 
Describe the error in the following ``proof'' that $0^*1^*$ is not a
regular language.  
(An error must exist because $0^*1^*$ {\em is} regular.) \\ 
The proof is by contradiction.  
Assume that $0^*1^*$ is regular.  
Let $p$ be the number of states in a DFA recognizing $0^*1^*$.
Choose $s$ to be the string $0^p1^p$.
You know that $s$ is a member of $0^*1^*$, but Example 1.73 (in the text)
shows that $s$ cannot be pumped.  
Thus you have a contradiction.  
So $0^*1^*$ is not regular.
\end{problem}

\begin{problem}
Sipser 1.47

Let $\Sigma=\{1, \# \}$ and let $$Y=\{w\mid w=x_1\#x_2\#\ldots\#x_k \mbox{ for } k\geq 0, \mbox{ each } x_i \in 1^*, \mbox{ and } x_i \not= x_j \mbox{ for } i\not = j\}.$$ Prove that $Y$ is not regular.
\end{problem}

\end{document}

