\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb,amsthm}
\pagestyle{empty}
\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~360 --- Introduction to the Theory of Computing\\
Fall 2017\\
Problem Set 2\\
\end{center}
\thispagestyle{empty}
\bigskip\bigskip
\noindent{\it Handed out Thursday, September 14, 2017}
\bigskip
\noindent{\it Due Thursday, September 21, 2017, at 5 PM. Submit to
LEARN.}
\bigskip\bigskip
\noindent 1. [10 marks]
\noindent Which of the following claims are true? Just answer ``true'' or
``false'' for each one. No justification necessary.
\begin{itemize}
\item[(a)] [2 marks] If $L$ is a language, then $L \emptyset = \emptyset$.
\item[(b)] [3 marks] $({\tt a}^2)^* = ({\tt a}^*)^2$ .
\item[(c)] [2 marks] ${\tt a}^n {\tt b}^n = ({\tt ab})^n$ for all $n$
\item[(d)] [3 marks] $\{ {\tt a, b} \}^* = ({\tt a}^* {\tt b}^*)^*$.
\end{itemize}
\bigskip
\noindent 2. [10 marks]
\noindent Give a regular expression, using only the operators union ($\cup$),
concatenation, and Kleene *, for each of the following. Give a brief
English explanation of your solution. No formal proof necessary.
Try to make your solutions as short as you can.
\begin{itemize}
\item[(a)] [3 marks] $\{ {\tt a,b,c} \}^* - {\tt a}^* {\tt b}^* {\tt c}^*$.
\item[(b)] [3 marks]
The set of strings over $\{ {\tt a,b} \}$ that do not contain
two (or more) consecutive occurrences of the same letter.
\item[(c)] [4 marks] The set of strings over $\lbrace {\tt a, b} \rbrace$
containing exactly
one pair of consecutive $\tt a$'s and exactly one pair
of consecutive $\tt b$'s.
\end{itemize}
\bigskip
\noindent 3. [10 marks]
\noindent Give a formal proof of the identity
$|xy| = |x| + |y|$ for strings $x, y$. Hint: use induction, and
be sure to say precisely what you are inducting on.
You can use the following recursive definition of length of a string:
$|\epsilon| = 0$, and for $c$ a single symbol we have
$|xc| = |x| + 1$.
\bigskip
\noindent 4. [Extra credit only; 5 marks]
\noindent The current record for the Post problem on strings mentioned in
Lecture \#2 (see the course home page for more info) seems to be
a string of length $43$ that achieves $20858070$ different strings
until a repetition occurs. Find an example, of length $\leq 500$,
that results in an even larger number of strings. Explain how you did it.
\end{document}