\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,xcolor}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 2} (due Feb 1 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 begin with $1010101$ and have length divisible by 5.
\item[(b)] All strings that do not begin with $101$ or $010$, and end with $00110$.
\item[(c)] All strings $x$ such that the number of ``leading zeros'' in $x$ is divisible by 3, and $x$ contains an odd number of ones.
(For example, the string $00000101001$ has 5 leading zeros and is not in the language; the string $101001$ has 0 leading zeros and is in the language.)
\item[(d)] All strings that have an even number of occurrences of $01$ as a substring.
(For example, 11110000 and 0000111101111 are in the language but 0000111100011100011 is not.)
\end{enumerate}
\bigskip
\bigskip
\item[Problem 2.2:]
Describe a DFA that accepts each of the following languages.
Describe briefly what each state in your DFA \emph{means}.
For (a)--(b), you should draw the complete DFA.
For (c), do not attempt to draw your DFA, since the number of states could be huge; instead,
give a mathematically precise description of the states $Q$,
the start state $s$, the accepting states $A$, and the transition function $\delta$.
\begin{enumerate}
\item[(a)] (25 points) All strings in $\{0,1\}^*$ that begin with $1010101$ and have an even number of zeros.
\textcolor{red}{[Hint: you may either use the product construction or give a direct solution (the latter uses fewer states).] }
\item[(b)] (30 points) All strings $x\in\{0,1\}^*$ that do not begin with $101$ or $010$, and end with $00110$.
[Hint: \textcolor{red}{{\bf do not}} use the product construction. \textcolor{red}{Give a direct solution instead. The number of states
should be under 15.}]
\item[(c)] (45 points) All strings $x\in\{0,1\}^*$ such that the number of 0's is divisible by 7 or the number of 1's is divisible by 11 or the number of occurrences of $01$ is even.
\end{enumerate}
\end{description}
\end{document}