\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}}
\DeclareMathOperator{\iq}{iq}
\thispagestyle{empty}
\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~462 --- Formal Languages and Parsing\\
Winter 2020\\
Problem Set 3\\
\end{center}
\bigskip
\noindent{\it Distributed Friday, January 24 2020.}
\smallskip
\noindent{\it Due Friday, January 31 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] If quotient were a true inverse to concatenation,
we might expect it to obey the identities
\begin{align*}
L_1/(L_2 L_3) &= (L_1/L_2)/L_3 \\
L_1/(L_2 L_3) &= (L_1/L_3)/L_2
\end{align*}
for all languages $L_1, L_2, L_3$.
For each of these two
identities, either prove it holds, or give a counterexample.
\bigskip
\item{} [10 marks]
(A variation on the quotient operation on
languages.) Let $L_1, L_2 \subseteq \Sigma^*$,
and define $\iq(L_1, L_2)$, the
infix quotient of $L_1$ and $L_2$, to be the language
$$\lbrace y \in \Sigma^* \ : \ \text{there exist } x, z \in L_2
\text{ such that } xyz \in L_1 \rbrace.$$
Prove that if $L_1$ is regular then $\iq(L_1, L_2)$ is regular.
\bigskip
\item{} [10 marks]
Suppose $L_1$ and $L_2$ are finite languages containing $m$ and $n$
strings, respectively, for $m, n \geq 1$.
\begin{itemize}
\item[(a)] Show that the language $L_1 L_2$ has at most $mn$ strings and
at least $m+n-1$ strings.
\item[(b)] Show, by a set of examples, that for each pair of integers
$m, n \geq 1$ there exist languages $L_1$ and $L_2$, containing
exactly $m$ and $n$ strings, respectively, such that
$L_1 L_2$ has exactly $m+n-1$ strings.
\end{itemize}
\end{enumerate}
\end{document}