\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{parskip}
\usepackage{tikz}
\usetikzlibrary{topaths,calc,automata,positioning}

\setlength{\arraycolsep}{4pt}

\begin{document}
\begin{center}
\section*{CS 360 --- Introduction to the Theory of Computing \\ Assignment 2}
\subsection*{University of Waterloo, Spring 2018}
\end{center}
{\it Due 5:00 PM, June 1, 2018.}

In this assignment, you are asked to determine whether or not the given language $L$ is regular. To show that $L$ is regular, provide a finite automaton or regular expression and/or argue using closure properties of regular languages. You do not need to make a formal induction argument---an informal argument that is enough to convince the marker will suffice. To show that $L$ is not regular, provide an argument using the pumping lemma and/or closure properties of regular languages.

\begin{enumerate}
\item 
Let $L = \{ a^k b w \mid w \in \{a,b\}^k, k \in \mathbb N \}$. Show whether or not $L$ is regular.

\item 
Let $L = \{ a^i b^j \mid i+j = 0 \bmod 4; i,j \in \mathbb N \}$. Show whether or not $L$ is regular.

\item 
Let $L = \{ a^m \mid m \neq n^2 \text{ for any $n \in \mathbb N$} \}$. Show whether or not $L$ is regular.

\item 
Let $\Sigma = \{A,C,G,T\}$ be the alphabet of DNA bases. Let $\theta : \Sigma^* \to \Sigma^*$ be an \emph{antimorphism}. An antimorphism is a mapping such that for $u,v \in \Sigma^*$, we have $\theta(uv) = \theta(v)\theta(u)$. We define $\theta$ by
\begin{equation*}
\theta(A) = T \quad \theta(C) = G \quad \theta(G) = C \quad \theta(T) = A.
\end{equation*}
We call $\theta$ the \emph{Watson-Crick involution}; given a DNA strand $w \in \Sigma^*$, $\theta(w)$ is the Watson-Crick complement of $w$. Observe that $\theta$ is an \emph{involution}, which means that it has the property that for any word $w \in \Sigma^*$, we have $\theta^2(w) = \theta(\theta(w)) = w$.

Let $L = \{w \in \Sigma^* \mid w = \theta(w) \}$. Show whether or not $L$ is regular.

\item 
Let $G$ be the following context-free grammar.
\begin{align*}
S & \to aSc \mid A \\
A & \to bA \mid \varepsilon
\end{align*}
\begin{enumerate}
\item What is the language generated by $G$? Argue informally about how $G$ generates this language.
\item Show whether or not $L(G)$ is regular.
\end{enumerate}



\end{enumerate}
\end{document}
