\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref}
\newcommand{\eps}{\varepsilon}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 4} (due Feb 20 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 4.1:]
Prove that the following languages are not regular by
using the fooling set method:
\begin{enumerate}
\item[(a)] $\{ ww^Rw \mid w\in \{0,1\}^*\}$
\item[(b)] $\{(01)^{k^2+k} \mid k\ge 0\}$
\item[(c)] $\{ \mbox{all strings in $\{0,1\}^*$ that contain a
palindrome of length at least 6 as a \emph{prefix}} \}$
(For example, ${\bf 1100011}01$ is in the language, but
$1110001101$ is not.)
\end{enumerate}
\bigskip
\item[Problem 4.2:]\
\begin{enumerate}
\item[(a)]
Prove that the following language is regular:
$$\{\mbox{all strings in $\{0,1\}^*$ that
do not contain any palindrome of length at least $6$ as a \emph{substring}}\}$$
Don't give a DFA or NFA\@. Rather, use closure properties
and basic facts about regular languages (for example, all finite
languages are regular).
[Hint: if a string contains a long palindrome, wouldn't it contain
a shorter one?]
\smallskip
\item[(b)]
Prove that the following language is not regular:
$$\{\mbox{all imbalanced strings in $\{0,1\}^*$ that
contains a balanced substring of length at least 6}\}$$
(Recall that
a string is \emph{balanced\/} iff it has the same number of 0's and 1's.
A string is \emph{imbalanced\/} iff it is not balanced.)
Don't use the fooling set method. Rather, use closure properties and a proof by contradiction.
You may use the result from Problem~2.3. And you
may also use the standard fact that $\{ w\in \{0,1\}^* \mid \#_0(w)=\#_1(w)\}$ is not regular.
\end{enumerate}
\bigskip
\item[Problem 4.3:]
Give a context-free grammar (CFG)
for each of the following languages in (a), (b), and~(d).
You must provide explanation for how
your grammar works, by describing in English what is generated by
each non-terminal. (Formal proofs of correctness are not required.)
\begin{enumerate}
\item[(a)] $\{w \in \{0,1\}^* \mid \mbox{$w$ is a palindrome of length at least $6$}\}$.
\item[(b)] $\{0^i1^j0^k \mid k=2i+3j,\ i,j,k\ge 0\}$.
\item[(c)] Convert your grammar from (b) into Chomsky normal form.%
\footnote{See Section~5.8 of
\href{http://jeffe.cs.illinois.edu/teaching/algorithms/models/05-context-free.pdf}{Jeff's book} for the precise definition.
To summarize, all production rules must be of the form $A\rightarrow BC$ or $A\rightarrow a$. For the start symbol $S$,
the rule $S\rightarrow\eps$ is allowed, but $S$ should not appear on the right-hand side of any rule.
}
\item[(d)] $\{w\in \{0,1\}^* \mid \mbox{$w$ contains at least $|w|/2$
consecutive 0's}\}$ (i.e., all strings of the form $x0^iy$ with
$i\ge |x|+|y|$).
\end{enumerate}
\end{description}
\end{document}