\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 - Spring 2024}
\chead{CM A02}
\rhead{Due Fri, June 7, 11:59 PM EST\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2024}

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

\providecommand{\SolutionProblemRegularExpression}{}
\providecommand{\SolutionProblemClosureProperties}{}
\providecommand{\SolutionProblemNonRegularLanguagesPartA}{}
\providecommand{\SolutionProblemNonRegularLanguagesPartB}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartA}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartB}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartC}{}
\providecommand{\SolutionProblemNonRegLongWordsPumpablePartD}{}
\providecommand{\SolutionProblemRegularCriterionPartA}{}
\providecommand{\SolutionProblemRegularCriterionPartB}{}
\providecommand{\SolutionProblemRegularCriterionPartC}{}

\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{[8]}$\Sigma = \{ 0, 1 \}$.
Give a \textbf{rigourous} proof for the equality of languages
\begin{displaymath}
L((10^{*})^{*}0) = L(0 + 1(0 + 1)^{*}0) .
\end{displaymath}
\SolutionProblemRegularExpression

\newpage

\item \label{ProblemClosureProperties} Closure Properties of Regular Languages\\
Let \rmp{[8]}$B$ and $C$ be languages over $\Sigma = \{ 0, 1 \}$.
Define the binary operation on languages
\begin{displaymath}
B \overset{1}{\leftarrow } C = \{ w \in B \ | \ \textrm{ for some } y \in C, n_{1}(w) = n_{1}(y) \} .
\end{displaymath}
Recall that $n_{1}(w)$ denotes the number of occurrences of the symbol $1$ in the string $w$.

For example, if $B = \{ 010, 101, 111 \}$ and $C = \{ 01, 011, 1111 \}$, then $B \overset{1}{\leftarrow } C = \{ 010, 101 \}$.

Prove that the class of regular languages is closed under the $\overset{1}{\leftarrow }$ operation.
\SolutionProblemClosureProperties

\newpage

\item \label{ProblemNonRegularLanguages} Non-regular languages\\
Prove that each of the following languages is not regular.

\vspace{3mm}

\begin{enumerate}
\item \label{ProblemNonRegularLanguagesPartA} $L_{a} = \{ 0^{i} 1^{j} \ | \ \gcd(i, j) = 1 \}$ over $\Sigma = \{ 0, 1 \}$ \rmp{[4]}
\SolutionProblemNonRegularLanguagesPartA

\newpage

\item \label{ProblemNonRegularLanguagesPartB} $L_{b} = \{ a^{m} \mid m \neq n^{2}$ for any $n \in \mathbb N \}$ over $\Sigma = \{ a \}$ \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{[4]} that $L = \{ a b^{j} c^{j} \ | \ j \geq 0 \}$ is not regular.
\SolutionProblemNonRegLongWordsPumpablePartA

\newpage

\item \label{ProblemNonRegLongWordsPumpablePartB} Prove\rmp{[4]} 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{RegularCriterion} Testing a Candidate Criterion for Regular Languages\\
Let $\Sigma = \{ 0, 1 \}$ be the alphabet for all languages in this problem.
\begin{enumerate}
\item \label{RegularCriterionPartA} Prove\rmp{[4]} that $L_{a} = \{ w \ | \ n_{0}(w) = n_{1}(w) \}$ is not regular.
\SolutionProblemRegularCriterionPartA

\newpage

\item \label{RegularCriterionPartB} Prove\rmp{[4]} that $L_{b} = \{ w \ | \ n_{0}(w) \neq n_{1}(w) \}$ is not regular.
\SolutionProblemRegularCriterionPartB

\newpage

\item \label{RegularCriterionPartC} Suppose\rmp{[4]} that $L$ is a language over $\Sigma $ and that there is a fixed integer $k \geq 0$ such that, for every $x \in \Sigma ^{*}, \ xz \in L$, for some string $z$ with $|z| \leq k$.
Does it follow that $L$ is regular?
Prove your answer.
\SolutionProblemRegularCriterionPartC
\end{enumerate}

\end{enumerate}

\end{document}