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

\newtheorem{DefinitionPlaceHolder}{Definition}
\newtheorem{DefinitionIntersection}[DefinitionPlaceHolder]{Definition}
\newtheorem{DefinitionUnion}[DefinitionPlaceHolder]{Definition}
\newtheorem{DefinitionSubSet}[DefinitionPlaceHolder]{Definition}
%\newtheorem{DefinitionPowerSet}[DefinitionPlaceHolder]{Definition}

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

\providecommand{\SolutionSets}{}
\providecommand{\SolutionLanguagesPartA}{}
\providecommand{\SolutionLanguagesPartB}{}
\providecommand{\SolutionDFAComputationPartA}{\vspace{8cm}}
\providecommand{\SolutionDFAComputationPartB}{\vspace{8cm}}
\providecommand{\SolutionDFAComputationPartC}{\vspace{8cm}}
\providecommand{\SolutionDFAComputationPartD}{\vspace{8cm}}
\providecommand{\SolutionDFAComputationPartE}{}
\providecommand{\SolutionDFAConstructionPartA}{}
\providecommand{\SolutionDFAConstructionPartB}{}
\providecommand{\SolutionExtendedTransitionFunctionPartA}{\vspace{10cm}}
\providecommand{\SolutionExtendedTransitionFunctionPartB}{}
\providecommand{\SolutionExtendedTransitionFunctionPartC}{}

\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 grading policy and rules on collaboration.  
}
\item{
Submit your completed solutions to \textbf{Crowdmark}.
}
\end{itemize}

\begin{enumerate}
\item \label{ProblemSets}

\begin{DefinitionIntersection} \label{DefinitionIntersection}
Let $X$ and $Y$ be sets.
Then the \textbf{intersection of $X$ and $Y$, denoted $X \cap Y$}, is the set of elements of both $X$ and $Y$:
\begin{displaymath}
X \cap Y = \{ z \ | \ z \in X \textrm{ and } z \in Y \}.
\end{displaymath}
\end{DefinitionIntersection}

\begin{DefinitionUnion} \label{DefinitionUnion}
Let $X$ and $Y$ be sets.
Then the \textbf{union of $X$ and $Y$, denoted $X \cup Y$}, is the set of elements of either $X$ or $Y$ (or both):
\begin{displaymath}
X \cup Y = \{ z \ | \ z \in X \textrm{ or } z \in Y \textrm{, or both}\}.
\end{displaymath}
\end{DefinitionUnion}

\begin{DefinitionSubSet} \label{DefinitionSubSet}
Let $X$ and $Y$ be sets.
Then \textbf{$Y$ is a subset of $X$, denoted $Y \subseteq X$}, if and only if every element of $Y$ is also an element of $X$.
\end{DefinitionSubSet}

Let \rmp{[6]}$X, Y$ and $Z$ be sets.
Rigourously prove this \textbf{set distributivity law}:
\begin{displaymath}
X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z) .
\end{displaymath}
\SolutionSets

\newpage

\item \label{ProblemLanguages}
Let $\Sigma $ be a non-empty finite alphabet.
Let $x, y \in \Sigma ^{*}$.
\begin{enumerate}
\item \label{ProblemLanguagesPartA} Prove\rmp{[4]} that, for all integers $i \geq 0$, we have $(xy)^{i}x = x(yx)^{i}$.
\SolutionLanguagesPartA

\newpage

\item \label{ProblemLanguagesPartB} Prove\rmp{[6]} that $xy = yx$ if and only if there exists a word $z \in \Sigma ^{*}$ such that $x^{2} y^{2} = z^{2}$.
\SolutionLanguagesPartB
\end{enumerate}

\newpage

\item \label{ProblemDFAComputation}
Consider the DFA, $M$, having alphabet $\Sigma = \{ 0, 1 \}$ and defined by the following diagram.

\begin{tikzpicture}[shorten >=1pt,node distance=3 cm,auto]
\node[state,initial] (q_{0}) {$q_{0}$};
\node[state] (q_{1}) [right of=q_{0}] {$q_{1}$};
\node[state,accepting] (q_{3}) [below of=q_{1}] {$q_{3}$};
\node[state] (q_{2}) [below of=q_{0}] {$q_{2}$};
\path[->]   (q_{0}) edge [below] node {1} (q_{1})
			(q_{1}) edge [bend right] [above] node {1} (q_{0})
            (q_{1}) edge [left] node {0} (q_{3})
			(q_{3}) edge [bend right] [right] node {0} (q_{1})
            (q_{0}) edge node {0} (q_{2})
			(q_{2}) edge [bend left] [left] node {0} (q_{0})
            (q_{2}) edge node {1} (q_{3})
			(q_{3}) edge [bend left] [below] node {1} (q_{2})
            ;
\end{tikzpicture}

\begin{enumerate}
\item \label{ProblemDFAComputationPartA}
Determine \rmp{[3]}whether or not $w_{a} = 0110 \in L(M)$.
Briefly justify your answer.
\SolutionDFAComputationPartA

\item \label{ProblemDFAComputationPartB}
Determine \rmp{[3]}whether or not $w_{b} = 10 \in L(M)$.
Briefly justify your answer.
\SolutionDFAComputationPartB

\newpage

\item \label{ProblemDFAComputationPartC}
Determine \rmp{[3]}whether or not $w_{c} = 010 \in L(M)$.
Briefly justify your answer.
\SolutionDFAComputationPartC

\item \label{ProblemDFAComputationPartD}
Determine \rmp{[3]}whether or not $w_{d} = 101 \in L(M)$.
Briefly justify your answer.
\SolutionDFAComputationPartD

\item \label{ProblemDFAComputationPartE}
Give \rmp{[1]}a brief description of $L(M)$.
No justification is required for the correctness of the description.
\SolutionDFAComputationPartE
\end{enumerate}

\newpage

\item \label{ProblemDFAConstruction}
Draw the diagram of a DFA, NFA or $\varepsilon$-NFA which accepts each of the following languages over $\Sigma = \{ 0, 1 \}$, and argue informally why your automaton accepts exactly the language given.
\begin{enumerate}
\item \label{ProblemDFAConstructionPartA} $L_{a} = \{ w \ | \ n_{0}(w) \equiv 0 \bmod 2 \}$ \rmp{[4]}
(Recall that $n_{0}(w)$ denotes the number of occurrences of the symbol $0$ in the string $w$.)
\SolutionDFAConstructionPartA

\newpage

\item \label{ProblemDFAConstructionPartB} $L_{b} = \{ w \ | \ n_{0}(w) \equiv 0 \bmod 2$ and each $0$ in $w$ is followed by at least one $1 \}$ \rmp{[6]}
\SolutionDFAConstructionPartB
\end{enumerate}

\newpage

\item \label{ProblemExtendedTransitionFunction}
Let $M = (\Sigma, Q , q_{0}, F, \delta)$ be a DFA.\\
Let $\hat{\delta}$ denote the extended transition function of $M$, as defined in the lecture slides.
\begin{enumerate}
\item \label{ProblemExtendedTransitionFunctionPartA} Prove \rmp{[4]}that, for any $x, y \in \Sigma ^{*}$, and any $q \in Q$, we have
\begin{displaymath}
\hat{\delta }(q, xy) = \hat{\delta }(\hat{\delta }(q, x), y) .
\end{displaymath}
\SolutionExtendedTransitionFunctionPartA

\newpage

\item \label{ProblemExtendedTransitionFunctionPartB} Assume \rmp{[4]}that for some state $q \in Q$, and for every $a \in \Sigma $, we have $\delta (q, a) = q$.
Prove that $\hat{\delta }(q, x) = q$ holds for every $x \in \Sigma ^{*}$. 
\SolutionExtendedTransitionFunctionPartB

\newpage

\item \label{ProblemExtendedTransitionFunctionPartC} Assume \rmp{[4]}that for some state $q \in Q$, and some string $x \in \Sigma ^{*}$, we have\\
$\hat{\delta }(q, x) = q$.
Prove that, for every $n \geq 0$, we have $\hat{\delta }(q, x^{n}) = q$. 
\SolutionExtendedTransitionFunctionPartC
\end{enumerate}

\end{enumerate}
\end{document}