\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 1\\
\end{center}
\bigskip
\noindent{\it Distributed Friday, January 10 2020.}
\smallskip
\noindent{\it Due Friday, January 17 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.
For the definitions of terms like reversal, subword, palindrome,
perfect shuffle, overlap, conjugate, etc., see the textbook.
Generally speaking, the level of detail in all problem sets should be
{\it enough to convince a skeptical TA}.
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]
Call a finite word $w$ ``reversal-closed'' if it
has the following property: $x$ a subword of $w$ implies
that $x^R$ is a subword of $w$.
Prove that a finite word $w$ is reversal-closed iff it is a palindrome.
\bigskip
\item{} [10 marks]
Give a recursive definition of the perfect shuffle of two identical-length
words, $x \, \sha \, y$. Then use that definition to give a
complete formal proof
by induction of the identity $(x \, \sha \, y)^R = y^R \, \sha \, x^R$.
Hint: use the recursive definition of reverse:
$\epsilon^R = \epsilon$, and $(xa)^R = a x^R$
for $a \in \Sigma$, $x \in \Sigma^*$. (You also might have to
prove some other properties of $\sha$ first.)
\bigskip
\item{} [10 marks]
An {\it overlap} is a word of the form $axaxa$, where $a$ is a single
letter, and $x$ is a (possibly empty) word. For example, the
word {\tt entente} is an overlap, with $a = {\tt e}$ and $x = {\tt nt}$.
A word is said to {\it avoid circular overlaps} if no conjugate of
a subword starts with an overlap. For example,
{\tt abcadeab} avoids circular overlaps. However,
{\tt eabcadeabcf} does not avoid circular overlaps:
consider the subword {\tt abcadeabc}; it has the conjugate
{\tt abcabcade} which starts with an overlap.
Prove that there is a function $f(k)$ such that
if the alphabet size is $k$, and $x$ avoids
circular overlaps, then $|x| \leq f(k)$. You should
state what $f(k)$ is as explicitly as possible.
The asymptotically best bound $f(k)$ found by
a student gets some extra credit marks.
\end{enumerate}
\end{document}