\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\HomeworkStart%
{4} % Homework number
{5} % Week of semester submitted
{1.0} % Version
\SaveIndent%
\HWInstructionsStd{}%
\begin{questions}[start=10]
\RestoreIndent%
\medskip%
\item \OLDHWProblem{100}{Irregularities.}{%
\RestoreIndent
\begin{questions}%[(A)]
\RestoreIndent%
\item \points{25} \itemlab{3:1:a}%
Prove that the following language is not regular by
providing a fooling set. You need to prove an infinite
fooling set and also prove that it is a valid fooling
set. The language is
\begin{align*}
L = \Set{\T0^kw\overline{w}\T1^k }{ 0 \le k \le 3, w \in
\{\T0,\T1\}^+},
\end{align*}
where $\overline{w}$ is the complement bit-wise not
operator. Formally, for
$w =w_1 w_2 \ldots w_m \in \brc{\T{0}, \T{1}}^*$, we define
$\overline{w} = \overline{w_1}\, \overline{w_2} \ldots
\overline{w_m}$, for $\overline{\T{0}} = \T{1}$ and
$\overline{\T{1}} = \T{0}$.
\medskip%
\item \points{25} Same as (A) for the following
language. Recall that a run in a string is a maximal
non-empty substring of identical symbols. Let $L$ be the
set of all strings in $\brc{\T0,\T1}^*$ that do not contain
any two distinct runs of \T0s of equal length. As an
examples, $L$:
\begin{compactitem}
\item contains any
string of the form $\T1^*\T0^*\T1^*$.
\item contains the strings \T{011001111} and
\T{0000001001000111000010}, and
\item does not contain the strings \T{010},
\T{00110110011} and \T{00001110000}.
\end{compactitem}
\smallskip%
\item \points{25} Suppose you are given two languages
$L, L'$ where $L$ is not regular, $L'$ is regular, and
$L \cap L'$ is regular. Prove that $L \cup L'$ is not
regular.
Also, provide a counter-example for the following claim (it
can be interpreted as an ``inverse'' of the above):
\medskip%
\noindent%
\textbf{Claim}: Consider two languages $L$ and $L'$. If $L$
is not regular, $L'$ is regular, and $L \cup L'$ is
regular, then $L \cap L'$ is regular.
\smallskip%
\item \points{25} (Hard\footnote{Don't feel bad if you can
not do this part. No hints would be given for this
part. We expect most solutions to be I{D}K for this
one.}) Same as (A) for
$L = \Set{\T0^{\ceil{n \lg n}}}{ n \geq 3}$, where
$\lg n = \log_2 n$.
\end{questions}
}{}{}{}
\medskip%
\item OLD \HWProblem{100}{Grammar.}{%
Describe a context free grammar for the following languages.
Clearly explain how they work and the role of each
non-terminal. Unclear grammars will receive little to no
credit.
\smallskip
\begin{questions}%[(A)]
\item \points{50}
$\Set{\T{a}^i\T{b}^j\T{c}^k\T{d}^\ell\T{e}^t}{ i,j,k,\ell,t
\ge 0 \text{ and } i+ j + k + \ell = t}$.
\smallskip
\item \points{50} (Harder.)
$L = \Set{ w \in \{\T0,\T1\}^*}{\text{ there is a prefix }x
\text{ of }w\text{\, s.t. }\#_{\T1}(x) > \#_{\T0}(x)}$.
\end{questions}
}{}{}{}
\medskip%
\item \OLDHWProblem{100}{As easy as a,b,c.}{%
Let $L = \Set{\T0^i\T1^j\T2^k}{ j = i+k}$.
\begin{questions}%[(A)]
\item \points{40} Prove that $L$ is context free by
describing a grammar for $L$.
\smallskip%
\item \points{60} Prove that your grammar is correct. (One
way to do it -- show that $L \subseteq L(G)$ and
$L(G) \subseteq L$, where $G$ is your grammar from the
previous part. This is not the only way.)
\end{questions}
}{}{}{}
\end{questions}
\HomeworkEnd{}