\documentclass[12pt]{article}
\usepackage{amsfonts, amssymb, amsmath, comment}
\usepackage[usenames,dvipsnames]{color}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{url}
\usepackage{xypic}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,shapes.geometric}
\usepackage{epsf}
\usepackage{epsfig}
\usepackage{enumitem}

\setlist[itemize]{nosep}
\setlist[enumerate]{nosep}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0in}
\parskip12pt
\parindent0pt
\pagestyle{fancy}
\lhead{CS 360 - Winter 2022}
\chead{CM A02}
\rhead{Due Wed, Feb 2, noon EST\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

\newcommand{\rmp}{\reversemarginpar\marginpar}

\providecommand{\SolutionProblemRegularExpression}{}
\providecommand{\SolutionProblemClosurePropertiesPartA}{}
\providecommand{\SolutionProblemClosurePropertiesPartB}{}
\providecommand{\SolutionProblemNonRegularLanguagesPartA}{}
\providecommand{\SolutionProblemNonRegularLanguagesPartB}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartA}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartB}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartC}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartD}{}
\providecommand{\SolutionProblemMoreClosurePropertiesPartA}{}
\providecommand{\SolutionProblemMoreClosurePropertiesPartB}{}

\input xy
\xyoption{all}

\begin{document}

\begin{itemize}
\item{
Start as early as possible, and contact the instructor if you get stuck.
}
\item{
See the course outline for details about the course's marking policy and rules on collaboration.  
}
\item{
Submit your completed solutions to \textbf{Crowdmark}.
}
\end{itemize}

\begin{enumerate}

\item \label{ProblemRegularExpression} Regular Expressions\\
Let \rmp{[6]}$\Sigma = \{ 0, 1 \}$.
Give a \textbf{rigourous} proof for the equality of languages
\begin{displaymath}
L((00^{*}1)^{*}1) = L(1 + 0(0 + 10)^{*}11) .
\end{displaymath}
\SolutionProblemRegularExpression

\newpage

\item \label{ProblemClosureProperties} Closure Properties of Regular Languages\\
Let $\Sigma$ be an alphabet.
Consider the following unary operation on languages over $\Sigma$:
\begin{displaymath}
Pref(L) = \left \{ w \ | \ \exists x \in \Sigma ^{*} \textrm{ such that } wx \in L \right \} .
\end{displaymath}
In this question you will supply the key content of two of the recursive cases for a proof by structural induction on $L$ that
\begin{quote}
if $L$ is regular, then it follows that $Pref(L)$ is also regular.
\end{quote}
In such a proof, we would be constructing new languages starting from regular languages $L_{1}$ and $L_{2}$, such that $Pref(L_{1})$ and $Pref(L_{2})$ are regular by our induction hypothesis.
(I encourage you to write down the rest of this proof in your spare time after you finish working on this assignment!)

\vspace{3mm}

\begin{enumerate}
\item \label{ProblemClosurePropertiesPartA}
Let \rmp{[6]}$L_{1}$ and $L_{2}$ be any languages over $\Sigma$, with $L_{2} \neq \emptyset$.
Give a \textbf{rigourous} proof of the equality of languages:
\begin{displaymath}
Pref(L_{1}L_{2}) = Pref(L_{1}) \cup \left ( L_{1} Pref(L_{2}) \right ).
\end{displaymath}
[\textbf{Remark:} We lose no generality in the proof of regularity by assuming $L_{2} \neq \emptyset$ here; if $L_{2} = \emptyset$, then $Pref(L_{1}L_{2}) = \emptyset$, which is regular by definition.]
\SolutionProblemClosurePropertiesPartA

\newpage

\item \label{ProblemClosurePropertiesPartB}
Let \rmp{[6]}$L_{1}$ be any language over $\Sigma$.
Give a \textbf{rigourous} proof of the equality of languages:
\begin{displaymath}
Pref(L_{1}^{*}) = L_{1}^{*} \cup \left ( L_{1}^{*} Pref(L_{1}) \right ).
\end{displaymath}
%If you re-use, check whether the RHS can be simplified to $L_{1}^{*} Pref(L_{1})$.
\SolutionProblemClosurePropertiesPartB

\end{enumerate}

\newpage

\item \label{ProblemNonRegularLanguages} Non-regular languages\\
Prove that each of the following languages over $\Sigma = \{ 0, 1 \}$ is not regular.

\vspace{3mm}

\begin{enumerate}
\item \label{ProblemNonRegularLanguagesPartA} Let $f(i)$ \rmp{[4]}be the $i$-th entry in the Fibonacci sequence ($f(1) = 1, f(2) = 1, f(i) = f(i-1) + f(i-2)$ when $i > 2$).
Then the language is
\begin{displaymath}
L_{a} = \left \{ 1^{f(i)} \mid i \geq 1 \right \} .
\end{displaymath}
\SolutionProblemNonRegularLanguagesPartA

\newpage

\item \label{ProblemNonRegularLanguagesPartB} $L_{b} = \{ 0^{i} 1^{j} \ | \ i \neq j \}$. \rmp{[4]}
\SolutionProblemNonRegularLanguagesPartB
\end{enumerate}

\newpage

\item \label{ProblemNonRegLongWordsPumpable} A Non-Regular Language In Which All Long Words Can Be Pumped\\
Let $\Sigma = \{ a, b, c \}$.

\vspace{3mm}

\begin{enumerate}
\item \label{ProblemNonRegLongWordsPumpablePartA} Prove\rmp{[3]} that $L = \{ a b^{j} c^{j} \ | \ j \geq 0 \}$ is not regular.
\SolutionProblemNonRegLongWordsPumpablePartA

\newpage

\item \label{ProblemNonRegLongWordsPumpablePartB} Prove\rmp{[3]} that $F = \{ a^{i} b^{j} c^{k} \ | \ i,j,k \geq 0$ and if $i = 1$ then $ j = k \}$ is not regular.
\SolutionProblemNonRegLongWordsPumpablePartB

\newpage

\item \label{ProblemNonRegLongWordsPumpablePartC} Exhibit\rmp{[4]} with proof a choice of a positive integer $n$, such that, for any $z \in F$ with $|z| \geq n$, we may write $z = uvw$ where
\begin{itemize}
\item{$|uv| \leq n$,}
\item{$|v| \geq 1$ and}
\item{$uv^{i}w \in F$, for all $i \geq 0$.}
\end{itemize}
\SolutionProblemNonRegLongWordsPumpablePartC

\newpage

\item \label{ProblemNonRegLongWordsPumpablePartD} Explain\rmp{[2]} briefly why the results of parts \ref{ProblemNonRegLongWordsPumpablePartB} and \ref{ProblemNonRegLongWordsPumpablePartC} do {\bf not} contradict the Pumping Lemma for regular languages.
\SolutionProblemNonRegLongWordsPumpablePartD

\end{enumerate}

\newpage

\item \label{ProblemMoreClosureProperties} More Closure Properties of Regular Languages\\
Let $\Sigma = \{ 0, 1 \}$ be the alphabet for all languages in this problem.
State whether each sentence given below is true or false.
If you think the statement is true, then prove it.
If you think the statement is false, then provide a counterexample and explain why your counterexample is correct.

\vspace{3mm}

\begin{enumerate}
\item \label{ProblemMoreClosurePropertiesPartA} If\rmp{[3]} $L_{1}$ is regular, $L_{2}$ is non-regular and $L_{1} \cap L_{2}$ is regular, then $L_{1} \cup L_{2}$ is non-regular.
\SolutionProblemMoreClosurePropertiesPartA

\newpage

\item \label{ProblemMoreClosurePropertiesPartB} If\rmp{[3]} $L_{1}$ is regular, $L_{2}$ is non-regular and $L_{1} \cap L_{2}$ is non-regular, then $L_{1} \cup L_{2}$ is non-regular.
\SolutionProblemMoreClosurePropertiesPartB
\end{enumerate}

\end{enumerate}

\end{document}