\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fullpage}
\usepackage[left=1.0in,top=1.0in,right=1.0in,bottom=1.25in]{geometry}
\usepackage{bbold}
\usepackage{tikz}
\usepackage{parskip}
\usetikzlibrary{topaths,calc,automata,positioning}
\pagenumbering{gobble}


\begin{document}
\begin{center}
\section*{CS 360 --- Assignment 1}
\subsection*{University of Waterloo, Spring 2018}
\end{center}
{\it Due 5:00 PM, May 18, 2018.}

\begin{enumerate}
\item 
Show for all words $u,v \in \Sigma^*$ and $k \in \mathbb N$, that $u(vu)^k = (uv)^k u$.

\item 
Consider the following DFA $A$:

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[shorten >=1pt,on grid,node distance=3cm,>=stealth,thick,auto]
    \node[state,initial,accepting] (0) {$q_0$};
    \node[state] (1) [right of=0]{$q_1$};
    \path[->]
        (0) edge [bend left] node {$0$} (1)
        (1) edge [bend left] node {$0$} (0)
        (0) edge [loop above] node {$1$} (0)
        (1) edge [loop above] node {$1$} (1)
        ;
\end{tikzpicture}
\end{center}
\end{figure}

\begin{enumerate}
\item Give the formal description for $A$.
\item What is the language that $A$ accepts? Prove this formally.
\end{enumerate}

\item 
Consider the language
\begin{equation*}
L = \{ w \in \{A,C,G,T\}^* \mid \text{$w$ ends in $AGG$, $CGG$, $GGG$, or $TGG$} \}.
\end{equation*}
Draw a state diagram for a DFA that accepts $L$ and prove formally that your DFA accepts $L$.

\item 
Prove that if $L$ is a regular language, the language
\begin{equation*}
L' = \{ u \in \Sigma^* \mid \text{$uv \in L$ for some $v \in \Sigma^*$} \}
\end{equation*}
is also regular.

\item 
The \emph{edit distance} of two words $x$ and $y$ is the minimum number of insertions, deletions, or substitutions of a symbol (collectively called \emph{edit operations}) to transform $x$ into $y$. For instance, we can transform the word $stars$ into the word $scarfs$ by one substitution ($t \to c$) and one insertion ($rs \to rfs$). Since two edit operations were necessary, the edit distance between $stars$ and $scarfs$ is 2. Similarly, we can transform the word $scarfs$ to $scarf$ by one deletion ($fs \to f$) for an edit distance of 1.

Give the state diagram and formal description of an $\varepsilon$-NFA that recognizes the language of all words over $\{a,b\}$ with edit distance at most 1 from the word $baa$. Give an informal description of how and why the machine works.

\end{enumerate}
\end{document}
