\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 A01}
\rhead{Due Wed, Jan 19, noon EST}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

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

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

\providecommand{\SolutionProblemPowerSetPartA}{}
\providecommand{\SolutionProblemPowerSetPartB}{\vspace{7cm}}
\providecommand{\SolutionProblemPowerSetPartC}{\vspace{7cm}}
\providecommand{\SolutionProblemTwoDifferentSubstrings}{\vspace{7cm}}
\providecommand{\SolutionProblemDFAComputationPartA}{\vspace{8cm}}
\providecommand{\SolutionProblemDFAComputationPartB}{}
\providecommand{\SolutionProblemDFAConstructionPartA}{}
\providecommand{\SolutionProblemDFAConstructionPartB}{}
\providecommand{\SolutionProblemDFAConstructionPartC}{}
\providecommand{\SolutionProblemExtendedTransitionFunctionPartA}{\vspace{10cm}}
\providecommand{\SolutionProblemExtendedTransitionFunctionPartB}{}
\providecommand{\SolutionProblemExtendedTransitionFunctionPartC}{}

\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{ProblemPowerSet}

\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}

\begin{DefinitionPowerSet} \label{DefinitionPowerSet}
Let $X$ be a set.
Then the \textbf{power set of $X$, denoted $P(X)$}, is defined to be the set of subsets of $X$.
In other words, $Y \in P(X)$ if and only if $Y \subseteq X$.
\end{DefinitionPowerSet}

\begin{enumerate}
\item \label{ProblemPowerSetPartA}
Let \rmp{[6]}$E$ and $F$ be sets.
Prove that $P(E) \cap P(F) = P(E \cap F)$.
\SolutionProblemPowerSetPartA

\newpage

\item \label{ProblemPowerSetPartB}
Let \rmp{[3]}$E$ and $F$ be sets.
Prove that $P(E) \cup P(F) \subseteq P(E \cup F)$.
\SolutionProblemPowerSetPartB

\newpage

\item \label{ProblemPowerSetPartC}
Give \rmp{[3]}an example of finite sets $E$ and $F$ such that $P(E \cup F) \not \subseteq P(E) \cup P(F)$.
Briefly explain why your choice of $E$ and $F$ is correct.
\SolutionProblemPowerSetPartC
\end{enumerate}

\newpage

\item \label{ProblemTwoDifferentSubstrings}
Let \rmp{[3]}$\Sigma = \{ 0, 1 \}$.
Let $L$ be the language, over $\Sigma$, or words having at least two different substrings, each of length $2$.
For example,
\begin{itemize}
\item $010 \in L$, because it contains the substrings $01$ and $10$, and
\item $000 \notin L$, because its only substring of length $2$ is $00$.
\end{itemize}
Describe $L$ by writing a sentence of the form
\begin{displaymath}L = \{ w \in \Sigma^{*} \ | \ P(w) \},
\end{displaymath}
where $P(w)$ is a first-order logic formula.
In $P(w)$, you may use the notation
\begin{itemize}
\item $|x|$ to return the length of any string $x$,
\item standard arithmetic relations $=, \neq, <, \leq,$ etc.,
\item standard arithmetic constants $0, 1, 2,$ etc., and
\item the relation $Substr(u,v)$, which is true if and only if $u$ is a substring of $v$.
\end{itemize}
\SolutionProblemTwoDifferentSubstrings

\newpage

\item \label{ProblemDFAComputation}
Consider the NFA, $M$, having alphabet $\Sigma = \{ 0, 1 \}$ and defined by the following diagram.
\begin{displaymath}
\entrymodifiers={++++[o][F-]}
\SelectTips{cm}{}
\xymatrix @-1pc {
*\txt{} \ar[r] & *++++[o][F=]{q_{0}} \ar@(ur,u)[]_{0} \ar[rr]^{1} \ar[dd]_{1} & *\txt{} & q_{1} \ar@(ur,u)[]_{0} \ar[dd]^{0} \ar@/^1pc/[ddll]_{1} \\
*\txt{} & *\txt{} & *\txt{} & *\txt{} \\
*\txt{} & q_{3} \ar@(dr,d)[]^{0} \ar@/^1pc/[uurr]_{1} & *\txt{} & *++++[o][F=]{q_{2}} \ar[ll]^{1} \\
}
\end{displaymath}
For each choice of input word $w$ given below, determine whether or not $w \in L(M)$.
Briefly justify each answer.
\begin{enumerate}
\item \label{ProblemDFAComputationPartA}
$w = 101$\rmp{[3]}
\SolutionProblemDFAComputationPartA

\newpage

\item \label{ProblemDFAComputationPartB}
$w = 1010$\rmp{[3]}
\SolutionProblemDFAComputationPartB
\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} = \left \{ w \in \Sigma ^{*} \ | \ n_{0}(w) \geq 2 \right \}$. \rmp{[4]}
Recall that $n_{0}(w)$ denotes the number of occurrences of the symbol $0$ in the string $w$.
\SolutionProblemDFAConstructionPartA

\newpage

\item \label{ProblemDFAConstructionPartB} $L_{b} = \left \{ w \in \Sigma ^{*} \ | \ w \textrm{ begins or ends with } 00 \textrm{ or } 11 \right \}$. \rmp{[4]}
\SolutionProblemDFAConstructionPartB

\newpage

\item \label{ProblemDFAConstructionPartC} $L_{c} = \left \{ w \in \Sigma ^{*} \ | \ n_{0}(w) \equiv 0 \bmod 2 \textrm{ and } n_{1}(w) \equiv 0 \bmod 2 \right \}$. \rmp{[4]}
\SolutionProblemDFAConstructionPartC
\end{enumerate}

\newpage

\item \label{ProblemExtendedTransitionFunction}
Let $M = (Q, \Sigma, \delta , q_{0}, F)$ 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}
\SolutionProblemExtendedTransitionFunctionPartA

\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 ^{*}$. 
\SolutionProblemExtendedTransitionFunctionPartB

\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$. 
\SolutionProblemExtendedTransitionFunctionPartC
\end{enumerate}

\end{enumerate}
\end{document}