\documentclass[12pt]{article}
\usepackage{fullpage,amssymb,amsmath}
\usepackage{cyrillic}
\def\sub{{\rm sub}}
\def\pref{{\rm pref}}
\def\suff{{\rm suff}}
\def\Pref{{\rm Pref}}
\usepackage[usenames]{color}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{breakurl}
\DeclareMathOperator{\iq}{iq}
\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~462 --- Formal Languages and Parsing\\
Winter 2020\\
Problem Set 4\\
\end{center}
\bigskip
\noindent{\it Distributed Friday, January 31 2020.}
\smallskip
\noindent{\it Due Friday, February 7 2020 by 5 PM. Hand in to LEARN.}
\bigskip\bigskip
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]
\begin{itemize}
\item[(a)] [4 marks]
Construct a finite-state transducer $T$ that
multiplies by $3$ in base $2$. More precisely,
$T$ should take the canonical representation of $n$
in base $2$, {\it starting with the
least significant digit\/}, and produce the canonical
representation of $3n$, again starting with the least
significant digit. You can assume the input has
no trailing zeros and you must ensure that the output also has
no trailing zeros. For example, if the input is
$1011$, then the output should be $111001$. On input
$\epsilon$ the output should be $\epsilon$.
Hint: use nondeterminism to handle the correct output
on the last few bits. Be sure to label which states
are final in $T$.
\item[(b)] [4 marks] Do the same thing, but where the input is given
{\it starting with the most significant digit}. Hint:
do (a) first, then reverse the direction of the transitions.
\item[(c)] [2 marks]
Explain why it is impossible for a {\it deterministic\/}
transducer to solve the problem in part (b). Hint:
what if the input is $\lfloor 2^n/3 \rfloor$ versus
$\lceil 2^n/3 \rceil$?
In all three parts, please
briefly justify correctness, but a complete formal proof
is not needed.
\end{itemize}
\bigskip
\item{} [10 marks] Let $s_k (n)$ denote the sum of the digits
of $n$, when expressed in base $k$. Thus, for example,
$s_2 (5) = 2$.
Using finite automata,
prove that $s_3 (13n) \not= 4$ for all $n \geq 0$.
Suggested outline:
first construct a DFA $M_1$ recognizing the
base-$3$ representations of multiples of $13$.
Next, construct another DFA $M_2$ recognizing those
$x \in \{ 0,1,2 \}^*$ such that the sum of the elements of
$x$ is equal to $4$. Next, create $M_3$ recognizing
the intersection of $L(M_1)$ and $L(M_2)$. Finally, observe that in $M_3$
there is no path from the initial state to a final state.
You can, if you wish, use any software for manipulating automata
that you find online. One possibility is {\tt Grail}, available
at \url{http://grail.smcs.upei.ca}. Provide complete details of
your computation, including any code that you wrote. A complete
formal proof is not needed.
(There are other ways to solve this problem, but I want you
to use automata.)
\bigskip
\item{} [10 marks]
Consider the following transformation on languages:
$$ {\tt sqrt} (L) = \lbrace x \in \Sigma^* \ : \ \text{ there exists }
y \in \Sigma^* \text{ such that } |xy| = |x|^2 \text{ and } xy \in L
\rbrace.$$
Show that if $L$ is regular, then so is ${\tt sqrt}(L)$. Hint: use
the boolean matrix approach and follow the general idea in
Proposition 3.8.8.
\end{enumerate}
\end{document}