\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}

\begin{document}

\topic{Induction and Regular Expressions}
\homework{7}

\maketitle

\begin{exercises}
\item
The city of Lineapolis is shaped like a circle, with a wall along the
perimeter. All roads in the city are perfectly straight lines, extending from
wall to wall. Every two roads intersect at a single point within the city, and no three roads
(or two roads and the wall) intersect at the same point. Every maximal region
within the city, not intersected by any road or wall, constitutes a city block.

When Lineapolis was built, the city planners faced the problem of deciding how
many blocks there would be if they built $n$ roads. You will help them solve
this problem.

\begin{enumerate}
\item Draw the first three cases $n = 1$, $n = 2$, $n = 3$. For each $n$, is
the number of city blocks the same regardless of how you draw the roads? If
not, show a counterexample. If yes, write down the number of blocks for $n = 1,
2$ and $3$.

\item Propose a relationship between $n$, the number of roads, and $B(n)$, the
number of blocks. No justification is necessary at this stage. ({\bf Hint:}
Study the structure of the pictures you drew in part (a) and draw more pictures
if you want.)

\item Prove the relationship you proposed in (b).

\item Lineapolis has two competing lines of coffeeshops. Each of the two
companies lobbies for exclusive rights to open shops in each city block. The
city council, however, wants to ensure that citizens always have a choice of
morning brew. As a compromise, the council votes that every block will be
allocated to a single coffee company, but no two adjacent blocks (that is,
blocks sharing a non-zero length of road) will be allocated to the same
company. Prove that this arrangement can always be satisfied, regardless of the
number of roads in Lineapolis.
\end{enumerate}

\item In this question we will give very precise inductive definitions of some
familiar string operations.  Recall that the set of strings $\Sigma^*$ is
defined inductively by the following rules:
\begin{itemize}
\item $\epsilon \in \Sigma^*$
\item for any $x \in \Sigma^*$ and $a \in \Sigma$, $xa \in \Sigma^*$.
\end{itemize}
\begin{enumerate}
\item Give an inductive definition of the length function $\ell : \Sigma^*
\rightarrow \mathbb{N}$.
\item Give an inductive definition of the concatenation function $c : \Sigma^*
\times \Sigma^*
\rightarrow \Sigma^*$, which takes two strings $x$ and $y$ and returns their
concatenation $xy$.
\item Prove inductively that $\ell(c(x,y)) = \ell(x) + \ell(y)$
\item Prove inductively that $c(c(x,y),z) = c(x,c(y,z))$
\item Prove inductively that $\hat{\delta}(\hat{\delta}(q,x), y) = \hat{\delta}(q,c(x,y))$
\end{enumerate}

\item Are the following sets regular?  If so, give a regular expression that
matches them.  If not, prove that the set is not regular.
\begin{enumerate}
\item $\{x \in \{0,1\}^* \mid |x| \geq 5\}$
\item $\Sigma^*$
\item Strings that alternate between 0 and 1
\item Strings with the same number of 0s and 1s
\item Strings of balanced parentheses (e.g. ``()()'', ``((()()))'', and ``'', but not ``())(()'').
\end{enumerate}

\item Prove or disprove: if $L$ is a regular set and $L' \subseteq L$, then $L'$
is also regular.

\end{exercises}

\end{document}
