\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{enumerate}
\usepackage[usenames]{color} 
\usepackage[pst-pdf=md5]{gastex}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\mfr}[1]{\mathfrak{#1}}
\newcommand{\mcal}[1]{\mathcal{#1}}
\newcommand{\pow}[1]{\mathcal{P}(#1)}

\newcommand{\ignore}[1]{}
\newcommand{\mybox}{\fbox}

\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\vpi}{\varphi}
\newcommand{\scl}[1]{{#1}^{\star}}
\newcommand{\ab}{\{a,b\}^{\star}}
\newcommand{\zo}{\{0,1\}^{\star}}
\newcommand{\sstar}{\Sigma^{\star}}

\DeclareMathOperator{\suff}{Suffix}


\begin{document}

\par\noindent{\bf CS81 HW\#7 Spring 2012} {\em Out: 03/01/2012. Due: 03/07/2012 (before class)}
\paragraph{Policy on homeworks}
\begin{enumerate}
\item {\em Collaboration}:
        You may discuss a question with any other student currently taking CS81 provided:
        (i) both of you contribute equally;
        (ii) you come away from any discussion with an understanding in your mind (and no archived solution of any form is retained);
        (iii) your submission is your own work prepared by yourself on a separate occassion.

\item {\em Reference materials}:
        You should only refer to materials from this semester of CS81
        (class notes, handouts, textbooks, grutors, instructor, etc).

\item {\em Submission}:
        Your submission should be legible or is prepared using TeX.
\end{enumerate}

\vspace{.1in}

\paragraph{Regular languages}
\begin{enumerate}[(A)]

\item Provide DFAs for the following languages.
\begin{enumerate}[(i)]
\item $L = \{w \in \zo : \mbox{$w$ contains the same number of $01$'s and $10$'s}\}$.
\item $L = \{w \in \zo : \mbox{$w$ is the binary representation of a number that is divisible by $3$}\}$.
\item $L = \{w \in (\{0,1\} \times \{0,1\} \times \{0,1\})^{\star}: \mbox{$w$ encodes binary addition}\}$.
	For example, 
	\[
	\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}
	\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
	\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}
	\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}
	\in L,
	\ \mbox{ but } \
	\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}
	\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
	\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}
	\not\in L.
	\]
\end{enumerate}

\item Consider the regular expression $R = (0 \cup 1(01^{\star}0)^{\star}1)^{\star}$.
	\begin{enumerate}[(i)]
	\item Find the smallest DFA you can construct for $L=L(R)$. 
	\item Describe succinctly what $L$ is: $L = \{w \in \zo : \mbox{$w$ is $\ldots$}\}$.
	\end{enumerate}

\item Consider the following assertions:
\begin{enumerate}[(1)]
\item If $L$ is regular, then so is $L^{c}$ (the complement of $L$).
	\begin{proof} (sketch)
	{\em If $L$ is regular, then there is an NFA $M$ that accepts $L$.
	Switch each state of $M$ from accepting to non-accepting and vice versa.
	Call the new machine be $M'$. Then $M'$ accepts of $L^{c}$.}
	\end{proof}
	Is the proof sketch above correct? If yes, provide the missing details (for example,
	why does $M'$ accept $L^{c}$). If not, explain what is wrong and provide the correct proof.
\item If $L_{1}$ and $L_{2}$ are regular, then so is $L_{1} \cap L_{2}$.
	\begin{proof} (sketch)
	{\em Note $L_{1} \cap L_{2} = (L_{1}^{c} \cup L_{2}^{c})^{c}$. Since regular languages are
	closed under union and complementation (see previous part), $L_{1} \cap L_{2}$ is regular.}
	\end{proof}
	\begin{enumerate}
	\item Is this proof sketch correct? If not, explain why and provide a correct proof.
		If yes, provide any missing details if any.
	\item Describe a direct construction of a DFA for $L_{1} \cap L_{2}$ from the DFAs 
		for $L_{1}$ and $L_{2}$.
	\end{enumerate}
\item If $L$ is regular, then so is $\suff(L)$, where
	$\suff(L) = \{w \in \sstar: xw \in L, \mbox{ for some $x \in \sstar$}\}$.
	\begin{proof} (sketch)
	{\em If $L$ is regular, then let $M$ be any DFA that accepts $L$. 
	Add $\epsilon$-moves from the start state of $M$, say $s$, to each state $q$ of $M$.
	Call the new machine $M'$. Then $M'$ accepts $\suff(L)$.}
	\end{proof}
	Is the proof sketch above correct? If yes, provide the missing details (for example,
	why does $M'$ accept $\suff(L)$). If not, explain what is wrong and provide the correct proof.
	
\end{enumerate}

\end{enumerate}

\end{document}

