\documentclass[12pt]{article}
\pagestyle{empty}
\usepackage{fullpage,amssymb,amsmath}
\usepackage{cyrillic}
\def\sub{{\rm sub}}
\def\pref{{\rm pref}}
\def\suff{{\rm suff}}
\def\Pref{{\rm Pref}}
\thispagestyle{empty}
\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~462 --- Formal Languages and Parsing\\
Winter 2020\\
Problem Set 2\\
\end{center}
\bigskip
\noindent{\it Distributed Friday, January 17 2020.}
\smallskip
\noindent{\it Due Friday, January 24 2020 by 5 PM. Hand in to LEARN.}
\bigskip\bigskip
{\it All answers should be accompanied by proofs.}
In all problems the underlying
alphabet $\Sigma$ is assumed to be finite.
Please use a document preparation system like LaTeX or Word for your
solutions. Do not handwrite solutions! For diagrams only, feel free to
draw them by hand if you like, and scan them.
\bigskip
\begin{enumerate}
\item{} [10 marks] Find a finite binary word $x$
that contains, as subwords, fewer than $|x|$ distinct
nonempty palindromes.
\item{} [10 marks] Prove the following improvement on Theorem~2.3.6
in the course text. You can use the same idea as in the proof of
that theorem.
Let $x$ and $y$ be nonempty words.
Show that
$x^\alpha = y^\beta$
for some fractional exponents $\alpha, \beta > 1$ satisfying
$\alpha + \beta \leq \alpha \beta$ iff
$xy = yx$.
\item{} [10 marks]
An infinite word ${\bf x} = a_0 a_1 a_2 \cdots$
is said to be {\sl recurrent} if every
subword that occurs in $\bf x$ occurs infinitely often in $\bf x$.
\begin{itemize}
\item[(a)] [5 marks] Show that an infinite word $\bf x$ is recurrent iff every
subword that occurs in $\bf x$, occurs at least twice.
\item[(b)] [5 marks]
Recall that a word $\bf w$ is ``reversal-closed'' if it
has the following property: $x$ a finite subword of $\bf w$ implies
that $x^R$ is a subword of $\bf w$.
Show that if an infinite word is reversal
closed, then it is recurrent.
\end{itemize}
\bigskip
\end{enumerate}
\end{document}