\documentclass[12pt]{article}
\pagestyle{empty}

\usepackage{fullpage,amssymb,amsmath}
%\usepackage{cyrillic}
\usepackage{epsfig}
\usepackage{float}

\DeclareMathOperator{\cyc}{cyc}

\thispagestyle{empty}

\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~462 --- Formal Languages and Parsing\\
Winter 2012\\
Problem Set 6\\
\end{center}

\bigskip

\noindent{\it Distributed Wednesday, February 8 2012.}

\smallskip

\noindent{\it Due Wednesday, February 15 2012, in class.}

\bigskip\bigskip

All answers should be accompanied by proofs.

\begin{enumerate}

\item{} [10 marks]
Using any method discussed in class, find the minimal DFA equivalent to the one whose
transition diagram is given below.  Show all steps.

\begin{figure}[H]
\begin{center}
\input p6f1.pstex_t
\end{center}
\vskip -.2in
\protect\label{diagram12}
\end{figure}

\item{} [10 marks]  
Recall from the last problem set that
$F_n \subseteq \lbrace {\tt 0,1,2,3,4} \rbrace^*$ is the
language defined as follows:
$$F_n = \lbrace {\tt 3} \ {\tt 0}^{i_1} \ {\tt 1} \ {\tt 0}^{i_2} \ {\tt 1}
\ \cdots {\tt 1} \ {\tt 0}^{i_n} \
{\tt 2}^k \ {\tt 0}^{i_k} \ {\tt 4}  \ : \ 1 \leq k \leq n, \ 1 \leq i_j \leq n
\rbrace .$$

Show that any DFA accepting the language $F_n$ must have at
least $n^n$ states.  Hint:  find $n^n$ pairwise inequivalent strings
under the Myhill-Nerode equivalence relation.


\item{} [10 marks] 
Let $\Sigma$ and $\Delta$ be alphabets, and let $w \in \Delta^*$.  We
say that a string $p \in \Sigma^*$ {\bf matches} $w$ if there exists a
non-erasing morphism $h:\Sigma^* \rightarrow \Delta^*$ such that
$h(p) = w$.  Here, ``non-erasing'' means $h(a) \not= \epsilon$ for all
$a \in \Sigma$.  You can think of $p$ as a ``pattern'' that is matching
$w$.  For example, if $\Sigma = \lbrace x \rbrace$ and $\Delta = \lbrace
{\tt a,b} \rbrace$, then the
pattern $xx$ matches the string {\tt abaaba}, since $h(xx) = {\tt abaaba}$
for $x = {\tt aba}$.

We define ${\rm Pat} (L)$ to be the set of all patterns in $\Sigma^*$ that
match at least one string in $L$.  For example, if
$\Sigma = \lbrace x, y \rbrace$ and $L = \lbrace a, abab \rbrace$,
then ${\rm Pat}(L) = \lbrace x, y, xx, yy, xy, yx, xyxy, yxyx \rbrace$.

Show that if $L$ is regular, then
${\rm Pat}(L)$ is regular.    Hint: use a construction based (in part)
on the transformation automaton.

\end{enumerate}

\end{document}