\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 2} (due Feb 6 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 2.1:]
For each of the
following languages over the alphabet $\{0,1\}$, give
a regular expression that describes that language, and briefly
argue why your expression is correct.
\begin{enumerate}
\item[(a)] All strings that contain $10110110$ or $1101$ as a substring.
\item[(b)] All strings that begin with $110$ and do {\bf not} end with $0110$.
\item[(c)] All strings $x$ such that the number of 0's in $x$
is divisible by 3 and $x$ contains $1101$ as a substring.
\item[(d)] All strings $x$ such that between any two 1's in $x$, the number of 0's is divisible by 3.
(For example, $0100010000001100$ is in the language, but $010001000000101$
is not.)
\end{enumerate}
\bigskip
\item[Problem 2.2:]
Describe a DFA that accepts each of the following languages
over the alphabet $\{0,1\}$.
Describe briefly what each state in your DFA \emph{means}.
\begin{enumerate}
\item[(a)] All strings that contain $101100$ as a substring.
\item[(b)] All strings $x$ such that the number of 0's in $x$
is divisible by 3 and $x$ does {\bf not} end in $110$.
[Hint: use the product construction.]
\item[(c)] All strings $x$ such that between any two 1's in $x$, the number of 0's is divisible by 3.
(For example, $0100010000001100$ is in the language, but $010001000000101$
is not.)
\end{enumerate}
\bigskip
\item[Problem 2.3:]
Describe a DFA that accepts each of the following languages.
Describe briefly what each state in your DFA \emph{means}.
Do not attempt to draw your DFA (the number of states could be huge\@!). Instead,
give a formal description of the states $Q$,
the start state $s$, the accepting states $A$, and the transition function $\delta$.
Describe briefly what each state in your DFA \emph{means}.
\begin{enumerate}
\item[(a)]
All strings in $\{0,1,2\}^*$ such that the number of 0's is divisible by 11, or the number of 1's is divisible by 13, or the number of 2's is divisible by 17.
\item[(b)]
The language $L$ from Problem 1.2, i.e.,
of all strings in $\{0,1\}^*$ that contain
a balanced substring with length at least 6.
(Recall that a string is \emph{balanced}
if it has the same number of 0's and 1's.)
[Hint: you may use the result from Problem 1.2.]
\end{enumerate}
\end{description}
\end{document}